When you have a new dedicated or virtual private server running with linux and Cpanel there are many settings that may need configuring before everything runs smoothly. I recently had problems with a vps where I could not add any add on domains in cpanel. The error message was:

Sorry, the domain is already pointed to an IP address that does not appear to use DNS servers associated with this server. ease transfer the domain to this servers nameservers or have your administrator add one of its nameservers to /etc/ips.remotedns and make the proper A entries on that remote nameserver.

The solution was to enable a setting in WHM under Tweak Settings:

Allow Creation of Parked/Addon Domains that resolve to other servers (i.e. domain transfers)

[Edit 23 Feb 2013] On the new version of cpanel/whm the setting is called:

Allow Remote Domains

Great website to check status of your site in case you have problems loading it in your browser:

http://www.downforeveryoneorjustme.com