The problem can be corrected by upgrading the affected package to version 1.6.7p5-1ubuntu4.2 (for Ubuntu 4.10), or 1.6.8p5-1ubuntu2.1 (for Ubuntu 5.04). In general, a standard system upgrade is sufficient to effect the necessary changes.
Details follow:
Charles Morris discovered a race condition in sudo which could lead to privilege escalation. If /etc/sudoers allowed a user the execution of selected programs, and this was followed by another line containing the pseudo-command "ALL", that user could execute arbitrary commands with sudo by creating symbolic links at a certain time.
Please note that this does not affect a standard Ubuntu installation.