|But it plays the videos in windowed mode? That's odd.|
If it doesn't play your videos at all, and all you get is audio, that's an easy fix, you need a codec pack like "K-Lite". But if it plays your videos in standard window mode, but not in full screen, then the problem isn't your player or your codecs, it's something with your graphics software, maybe graphics accelleration...and that's a bit over my head.
If you get impatient waiting for someone smarter than me to solve your problem, you could try playing with your display settings and seeing if you can get something to work. In the meantime, you may be able to help someone find your answers by telling us what media player your using, your operating system, and your graphics card. You can find your graphics card info in Device Manager under Display Adaptors, you can find Device Manager from your Start menu search.
I think most graphics cards have advanced settings in the Control Panel, I know NVIDIA does, and you could try changing some of those settings.