I think this happened because I changed the default install location for apps to sd card. I suspect this causes the unrevoked service (called "zyspkloit") to be installed to SD. As the SD card is unavailable immediately after boot, the service is unable to start.
The solution that worked for me:
1. Set your default app install location to "phone"
2. Use "manage applications" to uninstall "zyspkloit"
3. Re-run unrevoked
