i had the exact same issue with my 3GS..genius looked at it and replaced it with reconditioned phone which had the same issue, although not quite as bad. From what I understand, this is a pretty common problem.
Keep in mind the refurbs are just as good or better than new phones. The only pieces they keep from any used phone are the boards if the boards are working fine, because the boards are the expensive part. They put new glass, new battery, and new backing on it.