Telstra GPS + Paul Root ROM works!
For those that rooted with Paul's ROM, when you initially boot the phone up, it has no English Australia. I believe when you select English UK, it will automatically map to UK under google and will try to search for GPS satellite around UK. Obviously it failed. What I did was to scroll to Australia and in my situation to Victoria, the GPs locked in straight away.
Hope this help.