How do I get Location / GMap / Views setup to display non-US map nodes?
I can confirm that it is possible to get locations and GMAP running on Drupal 6 for Canadian addresses.  I have done this on more than one occasion. 

From your description it simply sounds some setting preventing the reverse geocoding of addresses. Edit one of your nodes with canadian addresses and confirm that the Lat and Lon field are empty.  Save then edit again and confirm it is still empty.

If the lat/lon fields are empty try the following 


Make sure you have a valid google maps API key for the URL you are running the site under.
Confirm that the location module has access to this API keys. Reverse geocoding settings for locations module is under /admin/settings/location/geocoding go to Canada and click "Configure parameters"   Or go there directly: /admin/settings/location/geocoding/ca/google  Your Gmap google map api key should be displayed.
Confirm that as a user you have permission to save lat/long info.  Under user permissions (/admin/user/permissions) go to "location module" and check that  "submit latitude/longitude" is selected for users that will be creating the nodes with address information. If not then there will be no reverse geocoding for any address, Canadian or otherwise.
Once you have confirmed the above, revisit a node with a Canadian address.  Edit and hit save. This will re-run the reverse geocoding.  If a lat/long is not saved then I will have to do some more digging. Also if you have lots of nodes in need of reverse geocoding, it is possible to do this programmatically.
Are you using CCK field or location module itself to save the address and lat/on? I am uncertain whether or not reverse geocoding works with the cck location field in D6.