Your T68i is fine for all GSM in North America and Europe so my guess is that the network was down, or that GSM in that area doesn't exist or is in the process of being implemented. TDMA if in that area, won't have been picked up on the t68, so maybe it is just lack of GSM.

Remember too that the map of coverage is their idealistic map in perfect conditions! Its not showing proposed coverage is it?