It seems that many people are getting this rather strange error when doing an update in a freshly installed Debian 4.0.
W: GPG error: http://security.debian.org etch/updates Release: Unknown error executing gpgv
The reason for this seems to simply be that the date on the machine is inaccurate. If you do the following (assuming that you have set up your timezone correctly), it should all be good again:
# apt-get install ntpdate
# ntpdate pool.ntp.org
# apt-get update
Have fun.
