I've just started using Krita with my Wacom tablet. At first it worked fine, but after a few minutes the brush on Krita began to lag. Is this normal?

No... It's a bit hard to do a long-distance diagnosis of what's going on on your system, though. Check whether opengl is enabled, check whether it helps to disable the Texture Buffer option, check whether playing with the brush spacing makes a difference.