Not the prettiest in the book, but you can use the CommandManager to invalidate all commandbinding:
CommandManager.InvalidateRequerySuggested();
http://stackoverflow.com/questions/1340302/wpf-how-to-force-a-command-to-re-evaluate-canexecute-via-its-commandbindings
http://msdn.microsoft.com/en-us/library/system.windows.input.commandmanager.invalidaterequerysuggested.aspx