I can't find the definitive answer.
I saw somewhere ubuntu9 is not supported, but I can't find the link
EDIT:
@LukeR.
Actually I performed the steps described the link you posted which are pretty much the normal way. The problem I had ( and now reading the link the poster did have too ) was installing the parallels tools.
From your link step 25:
...I’ll update this tutorial with the steps required to install Parallels Tools in Ubuntu 9.04 once Parallels updates (currently it doesn’t work).
Which lead me to this question. Parallels tools enable the use of full screen among other things ( afaik )