We get weak battery problems a lot at where I work. This is what I ask them:
How do you charge your phone? Do you have the charger plugged into the wall/car all the time, then you just plug your phone into it? If so, you're doing it wrong. You need to plug it into the phone first, and then into the power, and then when its done charging, you need to unplug it from the wall, and then the phone. I tell people to do this for about a week before coming back in (b/c the batteries we have are fairly expensive for replacements... $40 for a new one). It usually solves their problems.
One other thing...have you updated your phone recently? I know with Verizon phones its *228, then option 2 to update your roaming capabilites. My boss had that problem with her Razr a while back, and that seemed to help actually.