I always setup the A entries such as "server.thedomain.com"
Right, that's a correct hostname (though in a zone file it should have a period at the end otherwise the domain will get appended to the end again automatically)... however I'm saying that perhaps you should try using just 'servername' in the dns zone file... the dns server will append the zones domain to the end of it to make the full hostname... this is supposedly what cpanel is looking for. But I haven't confirmed that rumor, so it may not help anything.
Make the server hostname look like your 'mail' a record.
Code:
mail 14400 IN A ip.add.re.ss
instead of what you seem to have now:
Code:
mail.servername.com. 14400 IN A ip.add.re.ss
As I said it may not help... it was just someone's observation on this forum that the above was cpanel's behavior. So it's just hearsay.
Is it possible that the A entry error appears if the domain's nameservers have not been pointed to the actual server yet?
Err... what do you mean by this? So your domain's namserver's don't have proper A records either? Or your domain doesn't have the nameservers you're using listed at the registrar - ie parked? If that's true then its likely your problem, since a lookup of the server's hostname would return nothing if you don't have it setup at the nameserver's that are listed by the domain.