It occurred to me that George Georgalis wrote in gmane.os.netbsd.general:
>
> I had tried setting TERM but not using -T ...even with
>
>  env TERM=vt220 screen -T vt220
>
> the problem remains. The only thing I can identify as being
> different with other hosts is amd64 vs i386. can other people
> confirm color is working in screen on amd64?

libtermcap has an issue on amd64 - it's exposed even more when you try to
run screen. Try using 'xterm' as TERM setting - it did the trick for me.