Linux – sudo keeps asking me for the password in fish shell

sudo in Ubuntu keeps asking me for my password for every command. Previously, I only had to enter the password once, and then it would be remembered for a period of time. This recently changed, probably after "upgrading" to Natty.

I've done sudo visudo and set Defaults env_reset, timestamp_timeout = 60, tried rebooting, but it's still not working. How do I fix this?

After suggestions below, my /etc/sudoers looks like this:

#
# This file MUST be edited with the 'visudo' command as root.
#
# Please consider adding local content in /etc/sudoers.d/ instead of
# directly modifying this file.
#
# See the man page for details on how to write a sudoers file.
#
Defaults        env_reset
Defaults:endolith timestamp_timeout=60

# Host alias specification

# User alias specification

# Cmnd alias specification

# User privilege specification
root    ALL=(ALL:ALL) ALL

# Members of the admin group may gain root privileges
%admin ALL=(ALL) ALL

# Allow members of group sudo to execute any command
%sudo   ALL=(ALL:ALL) ALL

#includedir /etc/sudoers.d

Update:

I upgraded my VirtualBox and it started to suffer from the same problem. At a guess, I ran bash, and tried to sudo in that, and the password is remembered correctly. It's only when I use my default shell fish that it doesn't remember. It did in the previous Ubuntu release, but no longer.

Update:

I upgraded to 13.05 and this magically started working again. Now it asks for my password once, stops asking for a while, and then asks again after a period of time.