I'm not the best person to ask, but the last I heard, New Brunswick is the only officially bilingual province. The rest are either French or English only. (It was a news story when the premier of Manitoba spoke in French in his legislature a few weeks back).

That said, I live in Alberta now and normal serious parents tend to send their kids to French immersion. It's a leg up if you are going to get a government job, and it is pretty cool. That's not to say that John Q. Public is going to be happy if you are going to talk to him in French, but I think with the explosion of other languages in Alberta, the regressive types now are probably more accepting of it than they were before.

(Again this is just my observation, N=1, etc..)