yeah the "nokia messaging is preinstalled" is normal, i think you just have to go through that to set up the account though. nokia messaging does work as push for me but its been a while since i set it up i'm afraid i cant offer any more help than the wiki.

edit: it may be network related, i know nokia messaging were linking with orange over here to charge for push email, i know nothing of canadian networks though.