I had the same problem yesterday. It said unlocked but it really was not. I had to first do a hard reset on the phone. Then I flashed the newest htc rom from their website. After, you have to unlock the phone again using this link:
http://forum.ppcgeeks.com/showthread.php?t=36062
Then you should be able to flash to custom rom.