From this issue it seems to have been solved in mate-keyring 1.3.1: https://github.com/mate-desktop/mate-keyring/issues/2
. You can check your mate-keyring version with:
dpkg -l mate-keyring
Linux Mint 13 has on a clean install mate-keyring 1.3.0. Updating may provide a newer version, or you could enable the backports repository in the Software Sources program to upgrade to the newer MATE release (as also available on Linux Mint 14). Now, a fair disclaimer: I haven't tested Evolution on MATE so I'm not sure if this will actually fix it.
Another solution I found for an older Linux Mint version, which may still work fine: http://community.linuxmint.com/tutorial/view/848
You'd normally set the keyring password identical to your login password, or leave it blank (I can't recall which one works, or if they both do) and then you shouldn't be queried on the password each boot. Assuming the above fix. On GNOME you used to be able to edit your keyring password with Seahorse: http://community.linuxmint.com/tutorial/view/916
. If you go for the second approach, using the solution for an older Linux Mint version, for sure you can install and use Seahorse then.
All this stems from Evolution being a GNOME 3 project, and though MATE is based on GNOME 2 it renamed all the libraries and programs so as to not conflict with GNOME 3 (so you can install GNOME 3 and MATE side-by-side, which was not possible with GNOME 3 and 2). But, that causes these kind of problems