[citats]

First thing to note is the gps on the omnia pretty much sucks.
I'm also on Telus and this is what I must do to get the gps working everytime.
(first install google maps)
Launch google maps wait for a lock will take a few minutes the first time (or possibly subsequent times if it hasn't been used for a while)
Once you have your position ( it will say how many sats in the top right corner) then launch your favorite gps software and boom they get a lock immediately.
I use Bing (formerly Live) and Garmin... eventualy my map stops updating with Garmin on the omnia and I must exit the map view then go back in to have it start updating again.

My advice on gps and omnia... buy a stand alone.

*edit* also I don't think my omnia has ever locked on more then 5 sats, quite sad... my diamond can lock on 12 with any software.