Figured I'd post this just in case someone else has the problem. It may work for you. It may not. Your mileage may vary. Not valid in all 50 states. Batteries not included. Do not use while sleeping. Etc. Etc.

I was having problems with the game hitching and stuttering in some (seemingly random) areas and decided to turn things off one at a time to figure it out. I turned my water reflection quality and multisampling to medium and it went away.

At the launcher screen:
Options
Advanced
Water (tab)
Reflection Quality (dropdown list) -> Medium
Water Multisampling (dropdown list) -> Medium

I left everything else maxed out and haven't had any more wierd stuttering in odd places. I never had this issue with Fallout 3 but I'm sure something has changed in New Vegas that is probably causing it.

Just to be clear, it was happening to me even in areas where there is no water at all. After I set them to medium it stopped.

Oh yeah my system specs are:
Intel Core 2 Quad CPU Q9550 @ 2.83GHz
8GB RAM
NVIDIA GTX 280
Windows 7 Professional 64-bit

All vanilla with no overclocking or anything. Fallout: New Vegas and Fallout 3 run great!

Happy trails!

Update: Ok I'd be remiss if I didn't follow through on this with a bit of due diligence.

It seems I still get terrible framerates around lots of NPC's like in Vikki and Vance's Casino in Primm (walk to the right corner just after entering the place through the front door and then turn to face the people, wow stutter city). I guess I should mention that my previous post seems to have only cleared up my stuttering in areas with no or very few NPC's or bodies. Nothing I've tries seems to work in areas with lots of NPC's. *sigh* Oh well...

+1 here. I also have a fast machine, and I've noticed the 'npc stuttering' issues as well.

Specs:
AMD Phenom II X6 1090t
ATI Radeon 3870hd
4gb ddr3 ram
etc etc
Windows 7 x64

Yepp, the water fix works for the most part... the NPC thing is a glitch that will have to be patched though... oh well.

There is also ANOTHER possible glitch responsible where the game isn't using all your card's graphic power, effectively kneecapping your system specs as far as the game is concerned.

The water fix didn't work for me. It gave me a handful of extra frames, but the framerate still does ugly things when an NPC glances my way.