sounds like the phone has a hard time switching cell towers when you moving between different areas. Assuming its not a problem with the phone itself, you may want to go to the store and ask them to replace the SIM card. I've seen lots of connection problems that are resolved with a simple SIM card swap.
in the meantime, you probably dont need to reboot the phone each time. If you toggle airplane mode, that should reconnect the phone to the nearest tower(s).