I've not seen a problem like that but I think it has to be a resolution issue. Highly unlikely to be the Xbox itself. As long as it is region set to NTSC and all the ED/HD options (480p/720p/1080i) in the Video Settings are ticked all should be good.
Monitor trouble: possibly, you should check what resolutions it supports but I'd be surprised if it was this.
So that leaves the transcoder as the culprit and a few searches around the web suggest the Neoya had/has other issues although I can't find anything like this problem.
You say you've tried all the Xbox resolution settings, sorry if this too obvious but what about the Neoya x2vga2 resolution settings?
The info I found on it suggests it supports 480i/p, 720p and 1080i/p; is there a way to alter that manually?
It apparently has a LED indicating what resolution it is outputting, what does that show?
Have you tried just selecting one Xbox ED/HD resolution?
BTW when using a monitor be careful NOT to select a SD resolution by unchecking the ED/HD Xbox options ie. switching it to NTSC 480i. Most monitors won't support this and if the Xbox resolution settings are unprotected by a Shadow C you could be lining yourself up for some coniderable hassle unless you have a TV which supports 480i via Component too.