I had some videos that were quite large in size that windows media player had a tough time handling too.. VLC did fine without it but I got the k-lite codec pack and it fixed my windows media player problem
Be weary about where you get codecs from though, they're notorious for harboring stowaway malware.