there is a new build (5600) of parallels which is supposed to run better on the MBA. Auto update has never worked for me, so you may have to go to parallels' website and download the upgrade from there.
I know that the version that came in the box was really bad with Leopard. I discovered that the autoupdater was broken the day 10.5.1 came out. Haven't had any problems (other than the broken autoupdater) since then.