That is quite strange because you are even one version behind the latest Gingerbread build which is 6.12.181, not even counting the fact that ICS is out for the phone which is system version 6.16.211.
Are you able to access all other functions of the phone, download APPS and things from the Play Store. I am assuming phone calls, data, emails and what not are all working?
Have you called Verizon to make sure you device is registered on their network correctly? You could try to power down the phone, pull out the SIM card for 10 seconds, put it back in and boot up and try checking for system updates again.
Are you trying to check for updates on WIFI or only on the network, if you have not tried it while connected to WIFI you can check that again.