Do you have Parallels Tools installed? What is the max res on the monitor you are using for the OS X side? Have you tried increasing the amount of Video Memory that you allocate to Parallels?
Yes Parallels Tools is installed. I've looked around and it seems pretty common that Ubuntu only goes up to 1024x768. I have read that there is a way to increase this, and was just wondering if anyone knew how.