Depending on the type of service (bloody North American mishmash..) your provider offers, you may be able to improve things radically by getting a newer handset with more "bands".

I went from "fringe" here to full-bar simply by swapping my dual-band handset for a tri-band handset that doubled the number of cells it can talk to.

Cheers