OK, took the phone to a cell shop. They reflashed the phone for free (just in case). This is a Rogers phone and I was trying a t-mobile chip. The problem persisted with my chip.
The guy at the store had an active t-mobile chip which he installed, anf his worked fine!
I was heading to the US anyways, so I was going to go talk to T-Mobile about this. However, as soon as I crossed into the USA, the error went away! I was in the USA for 3 days, no problems at all.
As soon as I got back into Canada... the error shows up again!
Anyone got any ideas as to what is going on here??