OK, I have it working, but this is extremely kludgy! The problem seems to be somewhere in the OS or in ksystray that is making it confuse two different applications that are starting (all of the wrong icons that appeared before were apps that were starting at startup). So, I thought, since it's working when I start it manually, perhaps it just needs to wait a few seconds before going. I created the following script:

mannex@Leviathan:~$ cat maillaunch.sh
sleep 20
ksystraycmd evolution
mannex@Leviathan:~$

I set up this script in the system startup section, and it works (albeit with a 20 second delay). So, there is a bug here, but I'm not sure how to consistently reproduce it, and it may only be with Evolution, or with ksystraycmd, or with some other part of the OS. I wish I knew more info so I could file a bug, because this workaround, effective as it is, is also very, very ugly.

Thanks for all the help! I'm off and running!

It could be that the tray icon does not function properly if Plasma has not yet sufficiently started up. Autostart applications are started at the same time Plasma is.

That could be. I'm not sure how many people run Evolution under KDE, and since it's really more of a gnome/gtk program, it's look/feel is a bit out of place in KDE. It's the only startup program doing this. I had another gnome program as a startup that didn't do it (and then I found a KDE replacement). I have no problem with the 20 second delay (I could probably change it to ten or less) since in the first few seconds I'm busy logging in to the wallet, the firewall, etc. Thanks!