Now few things to cross check
1.I am not very familiar with ubuntu commands but can you tell us what output do you get after restarting vncserver services. Like do you get a "[OK]"
message which signs a successful restart.
2. have you checked your firewall and selinux which might be reason for not allowing clients to take remote.
to make sure you don't need to run the services every time you restart your server
#chkconfig --level 35 vncserver on