should depend on libcrypt-simple-perl

This bug was reported in Debian: http://bugs.debian.org/cgi-bin/bugreport.cgi?bug=353710
It is marked as fixed and the changelog of 1.7-1 says "Added dependency against libcrypt-simple-perl". In 1.8-1 it has been moved to Recommends: "debian/control: now recommends libcrypt-simple-perl and not depends on it".
libcrypt-simple-perl is not necessary to make checkgmail work properly so I think that putting it in Recommends is enough.

Feisty (and Edgy) contains checkgmail which Recommends: libcrypt-simple-perl.

I just installed checkgmail on Feisty and did not get libcrypt-simple-perl as part of the pack:

~$ checkgmail
GTK Accessibility Module initialized
Warning: Crypt::Simple not found ...

CheckGmail requires the above packages for password encryption
Please download and install from CPAN (http://search.cpan.org) if you want to use this feature ...

libcrypt-simple-perl not suggested by Synaptic when installing

Confirmed on my system with Gutsy. The package libcrypt-simple-perl has to be manually installed, checkgmail's package will not install it by default. This package is necessary to encrypt passwords and I vote for this bug to be fixed too.

I got no errors when I installed checkgmail with Automatix2. Try using Automatix to install it. It's better than Gmail's notifier...

This bug appears to be a sub-issue of bug #201555, so marking as duplicate.