DNS-Resolving fails irregularly (Ubuntu 12.04)

I just updated to Ubuntu 12.04.
After the update I cannot resolve hostnames reliably:
I use Konsole in Unity. There sometimes the DNS resolving works fine and suddenly after two commands or so it fails for the same address.

E.g. I ping a machine without DNS-Suffix (the suffix is shown in my network config correctly aside 3 valid nameserver IPs) and everything works fine. Then I try to log into the machine with the same address via ssh and I get a "Name or service not known".
Trying again, it works with a fully qualified name containing the suffix. I also had cases, when the IP wasn't resolved although I put in the fully qualified name. When I am more lucky, it starts working again with machine names only (without suffix, which is configured and worked perfectly up to now)

Is there probably a bug in the new Ubuntu Version?