If you're using the USB cable that came with the phone, you have to push it in there a bit, to get it to click in.
But, if you're doing that already, then warranty that sucker. If you bought it from a cellular provider store, take it there first. They may just exchange it on the spot, seeing...