1) Logged in to the registrar c/p of my domain and changed the nameservers to the ones of the new hosting company
2) Contacted the new hosting company to add the domain name to their DNS zone
Did I miss anything or all that is left to do now is wait a little while longer?
I would contact them directly but they have scr*wed me over in the past few months on several occassions and I don't trust them to contact them on this.
Try DNSReport to get a DNS check from a remote location or The-Cloak to access the site via a 3rd party proxy.