Just tried a debian vm at 640x480 and its fine, so I guess my project is back on, don't know why I was so hasty but at least I don't have to scrap my project
I don't know how the composite is implemented by the processor - the config.txt thread shows a few settings: specifically sdtv_mode and sdtv_aspect. It looks like you can use framebuffer_width and height too but to what effect I'm not sure. I guess we'll wait and see.
The point is that by dropping the chroma you might increase the possible resolution - the problem with composite is primarily the low bandwidth assigned to the chroma causing it to smear into a big mess at higher resolutions. FYI there's some information and some really good pictures at this wikipedia article:
You could get much better quality if you separate the signals out into component but that's not implemented here. I had the same idea before as one of the guys earlier in the thread (nice one!) - use teletext to implement stable colour text using composite - but, er, that might be impossible on this board
Nonetheless, I like it! Press teletext for help!
Still heading through the config.txt thread, dom says the PAL resolution is 720 x 576. That's "Pal DVD" resolution. I'm not sure what games are played in the processor to make that work. (Because you can't just do that resolution like a computer display and not expect it to look pants). Video would be ok though.