You can use other drivers to get full screen. I have a computer that 'xv' just flat out doesn't work (still don't understand why) but it has a GeForce 5200 (and I have OpenGL enabled) so I just use vo gl2. Full screen and no problems.
I don't know offhand which ones support fullscreen or not, but just do
and it will show you all the options you could use. I'd just keep trying until you find one that works.
Afterwards, I'd recommend making an alias in your ~/.bashrc file, so mplayer will ALWAYS use -vo new_vo rather than xv (I think you can also modify a certain file, but I don't really know the name off-hand) without having to type -vo new_vo.