What could cause "Permission denied" for command `crontab -e`?

Does /usr/bin/crontab have the setgid permission set?

-rwxr-sr-x 1 root crontab 32K 2008-09-28 14:07 /usr/bin/crontab*

If not, chmod g+s it (and if needed, chown before that)

Edit: Note that this only applies to Vixie Cron (used by most distros); other daemons (such as dcron) may use different permissions (setuid).

Also it's worth checking out the permissions at /var/spool/cron/crontabs by

ls -al /var/spool/cron/crontabs 

In my case doing this showed that actually the user assigned to the crontab was 'whoopsie' which I assume means there was some error in setting up the user.

Performing...

chown <username> /var/spool/cron/crontabs/<username>

Fixed this completely :)