My best guess is that Videotron is blocking some ports. Wind Mobile did something similar when they launched. Do any other instant messaging services work? How about Windows Live web messenger?
By the way, I can read French but I can't write it. If any of our bilingual users happen to stumble by, both myself and likely the OP would appreciate if you could post a translation.