Something is up for sure. I've shot plenty of concert video with my D5100 and had virtually no noticeable noise. It is probably too high an ISO.
A faster lens would help in some situations (eg: where depth of field isn't important) but for video I mostly use a 24-120mm f4 which isn't much different than your 18-200.
I wouldn't shoot at an ISO greater than 1600 so if you have ISO Auto on you'll need to set 1600 as the maximum sensitivity in the Shooting Menu. You can also set a minimum shutter speed in this menu which 1/60 is good.
If you then go to the Custom menu, assign the Function Button to AE-L (Hold). This way you can lock a particular exposure setting by pressing the AE-L button once, and a second time to release.
Locking exposure allows you to get the camera to choose the max ISO by panning to a dark scene then by locking the AE-L button, prevent the camera from adjusting the ISO on the fly. Setting the ISO to a max of 1600 will help reduce the noise.