thats your problem. the resolution of the videos is way smaller than the resolution of the phone. if you are converting these videos yourself, convert them to a larger size, specifically the size of your phone's resolution. if these are the only videos you have, upsizing them will not give you better quality, and will be larger file size, but will fit the phones screen.
on second thought, i'm not familiar with that device, but isn't there a zoom or full screen option on the phone's video player?