I recently created a simple workflow for an SP2010 site using SharePoint Designer 2010 which emailed a SharePoint Group when any document was uploaded to a specific document library. I found that for certain users the workflow would not start and nothing was logged in the workflow history list.
It seems that if the user uploading the document cannot see the membership of a SharePoint group they cannot resolve the email addresses of users within that group. The way around this is to edit the SharePoint group settings and set the "View Membership" setting to "Everyone" for the SharePoint group being emailed in the workflow. You can do this by going to Site Settings > People and Groups > Groups from the left hand navigation bar and editing the group in question.
This was also the case in MOSS 2007 and the problem and solution are described here: http://blogs.msdn.com/b/spdsupport/archive/2008/06/16/how-to-fix-sharepoint-designer-created-workflow-that-periodically-stops-and-does-not-send-emails.aspx