Couple thoughts ....
First, you retraced your steps a couple times? Did you look at
BlackBerry Technical Solution Center
Were you doing it on the handset, or on the web portal? Did you try on the both? If on the handset, did you try a hard reset, and then try again?
I would tend to think your rep is correct, but think odds are the handset is fine and the error is somewhere else. Post an update when you try the replacement. But try the original handset again after a while, before you return it.