Resolving subdomains don't work

Hello, i have following problem:

I try to explain as well as i can.

I changed hosting company so i modified the domain DNS1/DNS2.

After a day i was able to resolve it to correct ip of new server.

But i wasn't able to do it for subdomains (mail.domain.com,
forums.domain.com)

Then after like 6 hours, i was able to resolve subdomains.

Now after day i wasn't able to do so again.

So i did ipconfig /flushdns (i'm at windows xp) and it works fine again

But my friend reported he cannot ping the subdomains. (after 2 days of
domain dns change and subdomains created on new hosting NS)

What can be wrong ?

I thougt after domain is resolved, adding/delteing subdomains is real time -
as it was on my last hosting.

Any ideas ?

Thanks In Advance,
Dive