Problem has been resolved. I was unaware that unlocking the iPhone through the original carrier takes 2 steps:

1. The carrier gives you an unlock code;
2. You must perform a full restore via iTunes on your iPhone to 'fully unlock' the iPhone;

I was unaware of the iTunes step until I went to the Apple store. After performing a restore on the iPhone the SO SIM worked.

I hope that this helps other folks that may have similar issues.

Background:
1. I have an unlocked iPhone 4;
2. I bought a SO micro SIM and successfully activated it online;

What I see:
1. After I insert the SIM, the iPhone attempts to search for the NW and eventually "No Service" shows up;

What I've tried (with no success):
1. I've tried toggling Airplane Mode and then I get "Invalid SIM";
2. I've tried to switch my carrier manually - but the "Carrier" option under Settings is NOT available;
3. I've installed the SO SIM on my unlocked Nexus 4 and it works;
4. I've installed my (Virgin Mobile) SIM from my Nexus 4 into the iPhone 4 and the iPhone 4 works; Also, the iPhone with my Virgin Mobile SIM I can access the "Carrier" menu to manually select my network;
5. Resetting NW settings didn't work;
6. Resetting All settings didn't work;

Any thoughts or ideas would be appreciated!