Interesting. I've been having the same problems as you with dialling *777 and *888 using my Nokia E63 (and I just tried to call customer services, and the same problem too!)
Just noticed that the 3G indicator is always on these days – presumably there have been upgrades to the transmitters around here (Hamilton, ON) as I seldom saw this on my phone until recently – so I'll try to see if I can 'switch off 3G" and report back.
On the other hand… does this mean we can use 3G if we go with the unlimited data plan?