Check the pins inside the charger connection on the handset-if they have debris in them, or are bent, that may be the problem. Also, how long have you had the current battery? Is it the only one you have used in your Berry?
__________________ 1st Step in Troubleshooting: Do you have a BlackBerry Data Plan? 2nd Step in Troubleshooting: Pull the Battery.