DNS servers cache records for as long as what the record says it should be cached for.
When you go changing hosts the first step is always to change the DNS record's TTL (time to live) to a very short value (eg 1 minute)
That way you avoid your current problem completely.
As for clearing the cache (which can be done manually) you first need to work out if it is even on your end, if it is not local then there is nothing you can do but wait for the record to expire.
First you need to use dig to work out what is really happening
A quick look at my domain via my computer (Some extra output removed) :-
michael@indigo:~$ dig abnormalpenguin.com
;; ANSWER SECTION:
abnormalpenguin.com. 3600 IN A 126.96.36.199
;; AUTHORITY SECTION:
abnormalpenguin.com. 172800 IN NS ns2.tera-byte.com.
;; SERVER: 127.0.0.1#53(127.0.0.1)
The answer section gives the details about the record such as the IP address and the TTL (which is the number in the 2nd column) (also the TTL shown here is the TTL that is left on the server that returned the query)
The Authority section lists the DNS servers that host the domain
And the last line shows the DNS server that was actually used to look up the record.
Now if the Server is your own box and it is running named then you can use "rndc flush" to clear the record.
If the Server is some sort of home router device then the easiest way I can cover all of them is to simply say power toggle the thing.
If the Server is your ISP's DNS server or some other 3rd party then there is nothing you can do until the record expires.