Generally the message "The list of workflow actions on the server references an assembly that does not exist. Some actions will not be available. the assembly strong name is ..." occurs because the ACTIONS file doesn't match the assembly it references. Normally you would see that error because someone has extended the Workflow actions available in SPD with a custom action developed in Visual Studio. These custom actions are loaded when your workstation reads the WSS.ACTIONS file on the server. The file is located in the 12 hive under Template\1033\workflow. Your WSS.Actions file contains a reference to a custom action .dll which is not available on the server.
If you have verified that the assembly strong name is correct, verify that the ACTIONS file parameters match the assembly's activity properties. Be sure to check the "DependencyProperty.Register" methods too.