@Jayross: When you say that changing shutter speed does not affect your video, are you referring to the exposure level? Your problem could be that the ISO (or exposure level in general) is set to automatic, and it is compensating for your changes to shutter speed in order to maintain an EV 0 exposure by changing the other settings (ISO, aperture). Eg., as you increase shutter speed to get a darker scene, the camera might be boosting ISO to brighten the scene as a compensation because it always wants to expose at EV 0.
Before looking at a new camera, you might want to try updating the firmware, in case Nikon added the ability to manually control the exposure (assuming it is lacking on your version).
If it turns out that you really cannot control the exposure on that model of camera, I can say for sure that you can on the Canon EOS T2i/T3i. Those might not be your best options, but they are very good (but I recommend doing some serious research before replacing your camera).
Price point? Are you willing to switch brands?
@Jayross: I have my T2i and it's alright.
Remember: NIkon and Canon don't have AF. Or, well, they do, but it's shit. Keep this in mind when buying lenses: you don't want to constantly have to keep focusing if you choose to move the camera about. Canon's cameras have heat issues when recording video after a while. This constraint is sometimes limited by the fact that video can't be shot over x-length, due to filesize limitations of the FAT filesystem. AFAIK, Nikon also has filesystem issue. Usually battery and heat issues take precedence over filesize/20 minute limits, though. Sony also suffers from overheating at some point - but has much better AF.
Canon's 7D-and-above (5D, 1D) have better performance time-limit recording wise due to the magnesium-alloy body (metal conducts heat better than the T3i-and-below's body). Generally, Canon's 550D has better video then the 50D. All in all, T2i/550D is your best bet. Should leave you some money to buy a second lens (or a better beginning lens, if you buy body-only)
e: I hopr a nikon fan can chime in on Nikon. I'm not that well versed on the D5100.
e2: Here are some videos that can help give you a better idea. of 5100 vs t3i
note the T3i and T2i are practically identical, with the exception of the articulating screen. Might want to look at a 60D over a T3i as far as quality, and T2i for price.
The Nikon D5100 is much better than the D3100 for video, the tilty, swivelly screen actually makes quite a difference when filming video. Also you are able to plug an external mic in, something like the ME-1 or something a bit more fancy like the ones that clip on your shirt.
Overall though the D5100 is not much of an upgrade over the D3100 but as you already own the D3100 you would only need to buy the body and could probably get a pretty good price for your 3100 body.