Did you ever USE backup assistant to allow you to view your contact list on line? Just because the phone had it, if you never activated and used it, you didn't make an online backup, and the contacts were not backed up, and so you cannot get them.
If you did make an online backup, then you can retrieve it using BA on the replacement phone.
Lesson learned - use the tools available and BACK UP! Computer, phone, whatever....
