Sorry voor het engels (copy/paste), maar dit werkte bij mij...
Re: Evolution requires keyring after latest update
Here's how I fixed it (in 8.04):
System>Preferences>Encryption and Keyrings
In the Password Keyrings tab, select "default".
Click on Change Unlock Password.
Enter the old password (the one you've been prompted for when you start Evolution), but leave the new password fields blank.
It will prompt you with: Store Passwords Unencrypted?. Click on Use Unsafe Storage.
FYI, this is apparently "unsafe". Whatever. Now it no longer asks me for a default keyring password the first time I start Evolution after booting.
I still don't understand why this became a problem with the latest update to Evolution. I thought the point of having the libpam-gnome-keyring package installed was to make GDM automatically unlock your gnome keyrings when you login. Anyway, this worked for me.