I had a similar problem trying to run Evolution in Slackware. Admittedly, Evolution is not officially supported in Slackware, but... You might try running it from the command line to see if there are any errors or necessary libraries that might be missing.
You can re-run Evolution w/out rebooting though. Just run the command 'ps aux | grep evolution' (no quotes of course) and kill all the processes related to Evo like 'kill 10312 12132 15245' or whatever the PID's might be, then re-run it. Pain in the ass, but it works. I wound up switching to Mozilla for mail, calender, browser, contacts, etc. Very nice application suite, though not Outlook-like as Evo is.