It should work fine. Is this issue for specific user/role?
Try creating the workflow from admin role and publishing and testing once from admin role... then check for other roles.
If you have custom workflow activities then check that.
check event viewer if any information is logged
enable tracing to get detailed error message use the link http://support.microsoft.com/kb/907490
- Vijay