Default Verizon G2: Restricted Access Changed - TMo SIM

Got this error message when using a TMo SIM in a Verizon G2. I've only seen one thread about this for the G2.

Verizon G2s are SIM unlocked, right? So it shouldn't be a problem? I can put the TMo SIM in a TMo branded S2 and get full bars. I even tried the same SIM in a Verizon Galaxy S3 and got full bars.

I'm on VS98012B