I see there are some Telecom XT compatible, Android v1.6-bearing Sciphones on TradeMe for about $600.
Sciphone is a Chinese brand who have supported Android for a while now, at least since Q2 last year, but they can't quite get their hardware anywhere near the level of players like HTC and don't quite match even a lesser brand like General Mobile, who also sell the DSTL1 - a nice-looking Android phone.
The features and speeds look great......except for the small sdcards (2GB max). That tiny external storage limit is a killer. You'd want at *least* 4GB.
I can't find the first auction I saw 5 minutes ago. It looks likes it disappeared and this one below appeared - at a higher price. It's now $650.
The auction I can see now is here:
http://www.trademe.co.nz/Mobile-phones/Telecom-XT/auction-283626092.htm