Thanks gents for the help. Still having the problem with just company.com but the www.company.com
is going to the 000webhost.com website as we intended.
We currently use MS Office 365 for email which is just stellar, the Sharepoint not so stellar. Currently our DNS is pretty basic and as follows:
A company 126.96.36.199 1 Hour
CNAME www company.com 1 Hour
In the A record, I am not allowed to make company.com just company, so I suspect that is the problem, but what is weird about that is the WWW is pointing to company.com and that works. Bizarre.
So we are not in any critical stage anymore thanks to Mopedmaniacs (And others') help! Just this little annoyance which seems to be more with the MS Office 365 DNS manager than anything else at this stage.