There's a long thread here about broken USB ports.. Remember that the usb socket doesnt have to be loose and rattling round inside the device for the contacts to have broken off the motherboard..

If you've tried a different wire, different power source and removed the battery a while, I'd conclude that the connection inside the phone has a problem. You could take your wire/laptop/charger into a phone shop and ask if they will get out another phone (blackberry) that charges off this type of connector..
Or you can ask them to use their phone, their charger, and try your phone too.. which they may be more amenable to doing