Oh yeah, internet connection in rural areas could be an issue, although not necessarily an insurmountable one, depending on how much information was stored in the app itself. GPS works without an internet connection (although it can be slow without one), so if the game stored a world map and creature list internally, you wouldn't need to connect at all.
Finding persistent legendaries out in the wild could be an issue though, unless the game stored them in a hidden cache that updated when you returned to a location with internet access, and then you'd have to deal with the possibility of duplicates if two people caught the same target creature without updating the server-side data. Geocaching out in the wild could be problematic for the same reason.
The other concern is that the more data is stored in the app, the easier it is for hackers to cheat, which could be a problem if there was a real competitive side to the game. Although, if done well, for instance, more emphasis placed on a balanced metagame then on level grinding and getting the most powerful monsters, cheating to get rares wouldn't be such a big problem, even for competitive players. Note Pokemon, for instance - the game mechanics are complex enough that simply having lots of rare creatures or hard-to-access movesets doesn't do much to assure victory against other players, instead it is presumed that any possible 'mon and moveset combination may potentially be used in a tournament and emphasis is placed instead on creatively using the possibilities allowed by the game.