That's interesting. Since you replaced the battery and the problem still persists I would think that replacing the Dock Connector would be your next best step to take. The only other problem I could think of would be that the cable you were using was faulty, but it sounds like you've tried that already.
There is a repair manual for that procedure with a list of tools and parts you'll need, as well as the instructions to do the replacement.
[guide|4889]
Hopefully that'll solve your problem!