I've been shooting bands in nightclubs for years. First thing I learned was, if I wanted consistantly good results, shoot only in clubs with good lighting
Those photos you linked above appear to be shot in fairly large venues, which will necessarily have pretty strong lighting (the dancers in the second and third shots are in spotlight, for example). Things have to be really well-lit for the audience that's further away.
The two main things under your control are lens speed (okay, as under your control as budget will allow) and film/sensor ISO rating. Remember an f/2 lens will let you use a 1/125 shutter where an f/4 will only allow you 1/30 on the same shot. Back in the day, I used to shoot Kodak Ektar 1000 as much as possible in clubs - it had grain and saturation as good as any ISO400, but allowed an extra 1-1/3 stops of exposure. With my DRebel now, I usually shoot ISO800 in clubs and get great results.
I'll usually try to combine amient/stage lighting with flash, something that's particularly easy with the 420EX dedicated flash: I set the camera to manual, aperture wide-open, shutter generally around 1/60 (little slower if the lighting is particularly poor, but 1/60 calms the bulk of nasty motion blur), and let the E-TTL metering handle the flash. I also usually use a bounce diffuser on the flash if the stage background is really dark (all that blackness makes the E-TTL overcompensate sometimes) or if I'm shooting really close.
When it works well, you get not only a good balance of object colors AND lighting colors, but the shutter allows just a little motion blur to give a feeling of "action" while the flash freezes the "foreground" picture well.
Some examples are Molten Image
http://www.moltenimage.com +