Are mainly going with PC gaming, or console gaming? There is a thread which compares a few gaming headsets, you should check it out, too.
I use my Audio Technica AD700s with an Astro MixAmp for console gaming, and they really changed how I played the game... Even though I was doing just fine with my TV speakers. The AD700s did pretty well with PC gaming, also... Even though I am not nearly as competitive when it comes to PC gaming, so I am fine with speakers. Now that I have the AKG K701s, I pretty much only use the AD700s as gaming headphones.
A caveat, I tried my Sennheiser HD555s with the MixAmp and Modern Warfare 2, and instantly took them off in favor of the AD700s. Maybe I'll try them again, but the HD555s where very sharp sounding (not in a good way). The treble was way to sharp and loud and almost gave me a headache after one minute.
I also use a clip on mic, witch for whatever reason doesn't pick up my voice when it is CLIPPED ON, so I just fashioned a simple boom out of pipe cleaners... You know, those arts and crafts fuzzy wire things.
As mentioned, the DT880s are also a common suggestion. I haven't tried them with gaming, but while listening to music they really sounded really "filled." If that makes sense. The DT880s are next on my list to get. :s
An Xbox pal of mine had the Tritton AX360s and told me they were pretty decent, but they broke (apparently pretty easily) so he got the Tritton AxPros, which he said were really nice and a good upgrade from his Ax360s and Turtle Beach X1s. I can't comment on them as I have not tried them personally... Now, the Turtle Beach X4s, I honestly do not care for, my roommate had them so I had some time to base an opinion. The bass was extremely overpowering, yeah you really get to hear those grenades exploding, but the rest of the spectrum would just get overpowered. The positioning of the X4s were also lacking, especially after I started using the MixAmp and AD700 combo. If you go to Best Buy, they should have a small demo station set up with the X41s and X11s (with their Dolby Headphone decoder)... When I gave them both a try, the X11 combo sounded much nicer to me than the X41s, and the combo is about $50 or so bellow. The nice thing with the X11 combo, is you can use other headsets with it (ala the Astro MixAmp).