Situation
Workflow created in SPD and set up to activate upon the receipt of a new item being created in an emailed enabled list. Worked fine before SP1 was installed

Issue
When the email was received in the list, the workflow did not automatically start. The workflow worked fine if started manually. I had read that this action was disabled by design in SP1, but had also read that there would be a fix in the infrastructure update. After applying this the issue remained.

Resolution
Bit of digging unearthed this link which breaks down why this all happended. Suffice to say that running the command "stsadm.exe –o setproperty –propertyname declarativeworkflowautostartonemailenabled –propertyvalue yes" worked on my farm. Check this out first on your test hardware.

UPDATE: Just migrated my farm onto new hardware and could not get the above command to work on the new web front ends. This version did the trick;

stsadm -o setproperty -pn declarativeworkflowautostartonemailenabled -pv true

I also found that I had to turn off allowing each document library to recieve e-mail and then back on again to get it to work on the new server. This was of course after I changed all the email settings to reflect the new server details.