TellyMate Shield - TV output for Arduino

Your website says the characters are 38x25 characters.
What are you considering the video's full screen resolution?

Display resolution is irrelevant. The limiting factor is that the AVR CPU used can only output so many dots per scan line...