Solved my problem. If anyone experiences this, your SIM is a bit old. I went to my provider and got a new 128k SIM. It looks very different to my old one and works every time with the One V.
Just seems the phone isn't as compatible with older SIMs.
Current phone: Nexus 4 16GB
Retired: HTC One XL 32GB - Grey | HTC One V - Black | Motorola Defy - Green Lens