I usually thouroughly clean my PC once every couple months (disassemble it, and blowoff everything with canned air) then I blow out all the fans once a week with canned air - so those are clean. I have two case fans, one in front blowing in, one in back blowing out, as well as vents and the fan on the power supply blowing out, in addition to the fan on the video card, CPU, and HD fans.

I also had SpeedFan prior to this problem, and checked it. Everything -seemed- to be cool enough. Granted I didn't have anything to compare it to temperature wise for my video card. Let me know what data you want from the program and I'll see if I can get it.

As for how old the computer is I'd have to say the video card is the oldest, most everything else in it is maybe 2 years old at the most. I've actaully been meaning to get a new video card, and it appears that may be my only choice if this one is failing. However i did swap in a different video card, and had the same issues, is it possible they're both failing? Since I honestly wasn't sure if the one I swapped in was 100% working or not anyway, although when I took it out of the other computer maybe 6 months ago it was in working order.

The power supply is 400W, and I can't seem to find the brand anywhere - it's just the power supply I had from my old Compaq before I upgraded cases. I'm also not very knowledgable about power supplies, so any other insight would be helpful.

OK... so the video-card itself seems to be eliminated.
I would lean towards the PSU... if this one's from an older PC, you have to allow for wear/tear from that unit.

The capacitors inside it will lose a little power every year... and eventually it won't have enough juice for the demands made on it by other hardware.This is a normal occurance. Every PSU will lose a certain percentage annually... even the best-quality aftermarket units.
The best way to be certain-- is to have it tested at a shop. If you pull it out it should not cost much.
You can use the PSU calculator in my sig to see what you require for wattage-- a good idea as you don't want to under-power.Be sure to add all your hardware.
The PSU is the most-overlooked piece of gear... and it is one of the most important. The foundation of a house is a good analogy-- if it's no good, everything is out of whack

Just for an experiment can you try installing VLC and playing the videos with that?

Try a couple and post back the results

Also, I'm doubtful it's a hardware issue as gaming is fine which is much more intense on everything than playing videos. Just my opinion though.

Okay, I tried the PSU calculator and it came out to 384 Watts recommended, so that may very well be the problem at this point if everything is sucking too much power out of my already drained power supply. Would it still be worth while to bring it into a shop to have it tested?

I also tried the VLC media player with two different videos (MPEG and AVI) and it had the same problems as the others, slows my computer down and eventually just freezes.

If you pull the PSU out and take it to a shop--they will test it for you.
Is it worth it? I would say no-- it's probably time anyway.
The thing is --the PSU is the likeliest culprit... but there's no way to be certain it's the only culprit.
I'd say the odds are about 95 out of a hundred-- but there could also be a mobo issue-- not likely-- but it can't be ruled out either.

I'd go for something around 450-550W from a good maker like Enermax
Silverstone
PC Power & Cooling

models with larger fans are quieter (mine has 120mm fan)

Here's a few:

Newegg.com - Buy Computer Parts, PC Components, Laptop Computers, Digital Cameras and more!
there are others...that was a quick search. Be sure to check the user reviews.

Yeah, my motherboard is only maybe 6 months old, so I hope it wouldn't be that yet.

Thanks for the link, I'll look into some power supplies.