[UPDATE] The issue is apparently the result of an engineering constraint of the Nexus S and not simply a decision on T-Mobile’s behalf to block 3G video calls. Google must have corrected these issues with the Nexus S 4G, or it may simply boil down to an issue of chance when trying to use video calls over 3G.
The Nexus S received native video chat support via GTalk through the recent Android 2.3.4 update, but if you have the Google handset on T-Mobile you might be having a bit of trouble using the new feature over a 3G connection. Carriers apparently have the final say in exactly how video chat is enabled, and TMo has decided to only allow such calls over a Wi-Fi connection.
This isn’t the case with Sprint’s Nexus S 4G. Video chat works both over a cellular data connection and Wi-Fi. Their Nexus S also is cat approved, as evidenced by the below video.