Change the name of the Sharepoint workflow

For SharePoint Designer, the solution is similar to Dave's solution.
It seems SharePoint Designer saves local copies of DLLs from your servers, and although everything seems OK, this prevents it from updating the workflow (this is when custom activities are involved, which the question didn't mention).

To solve this issue:

1. Close SharePoint Designer

2. Go to

   %LOCALAPPDATA%\Microsoft\WebsiteCache

   Or, on older versions of windows:

   C:\Documents and Settings\%USER%\Local Settings\Application Data\Microsoft\WebSiteCache

3. Delete either (choose one, based on how annoyed you are by now):

   1. All folders.
   2. The folder that "looks most like your site" (can be more than one: site, site(1), etc, and should be the bottom level site, not the root site)
   3. The relevant DLL in that folder.
4. Start SharePoint Designer, save the workflow again, it should be ok.

Source: http://social.msdn.microsoft.com/forums/en-US/sharepointworkflow/thread/a4c77c18-e845-4121-9538-e76a44a82b88/:

Here's some guidelines, the main statement though is:

The general guideline for evolving the content type IA is to never change or rename content types or their aspects, make new ones and hide the old ones.