This sounds like a DNS vs Wins issue. When you ping your first name, you get a DNS resolution. When you do your nbtstat, you get a WINS resolution. One does not talk to the other to maintain their databases. When you ping the new name, you probably get a WINS resolution, which is why it works.
See if your DNS database has the first name in there. If you don't have DNS database access, do a nslookup or remove the DNS settings of your TCPIP properties and try again.