Okay, I've got some relatively good news.
That tool that I mentioned, well it works to put it bluntly.
I was able to get a lock on 7 sattelites in Google Maps, BUT the tool had to run in the background. I believe the root cause of the problem is that the Com4 or whatever ports are not being opened properly on my ROMs, Why? I have no clue.
Link to the tool if you want to try it out:
http://forum.xda-developers.com/showthread.php?t=360477