No, I think it should be perfectly (well I hope so) able to route from A to B. I’m not aware that you need to enter a country code on a Garmin, but I don’t have a Nuvi.
Can you search for a city first and then search for the street name? That should work around the Country/State problem…