I tried replacing my phone.apk with one that was "the perfect phone.apk". It could be done using root explorer. As soon as I did, I lost signal, and my IMEI no. A factory reset and reflashing VillainROM didn't help.
Luckily I had a backup that I had taken a month back using EFS Pro (Original Development section). I restored with that - but still it didn't show up. It was messed up pretty bad. So I restored and then flashed the stock ROM using ODIN. I then rooted, flashed VillainROM and restored all apps with TB. Saved!
Still, thanks a lot for the helpful guide vaskodogamagmail - I probably will need this one day