Today I picked up the phone to give GOOG-411 another test drive, and was thrown back after hearing the prompt "What city and province?". Surely this thing doesn't work for Canada now -- so I said "Regina Saskatchewan". Sure enough, "Please say a business name or category" -- the service now works exactly the same in Canada as it does in the US!
Just like when using it to find businesses in the US, I can get Google to connect me to the listed Canadian businesses too. I would be interested in knowing, if you are outside Canada & the US, if the service works in your country too. I tried London England without any luck -- so I'm going to guess that it's simply North America for right now.
Good job Google -- I'm glad you have finally brought the service to Canada, now we're just waiting for the rest of the world!