ICommand CanExecute not triggering after PropertyChanged?

The ICommand interface exposes an event ICommand.CanExecuteChanged which is used to inform the UI when to re-determine the IsEnabled state of command driven UI components.

Depending upon the implementation of the RelayCommand you are using, you may need to raise this event; Many implementations expose a method such as RelayCommand.RaiseCanExecuteChanged() which you can invoke to force the UI to refresh.

Some implementations of the RelayCommand make use of CommandManager.RequerySuggested, in which case you will need to call CommandManager.InvalidateRequerySuggested() to force the UI to refresh.

Long story short, you will need to call one of these methods from your property setter.

Update

As the state of the button is being determined when the active focus is changing, I believe the CommandManager is being used. So in the setter of your property, after assigning the backing field, invoke CommandManager.InvalidateRequerySuggested().

Update 2

The RelayCommand implementation is from the MVVM light toolkit. When consumed from WPF/.NET, the implementation wraps the methods and events exposed from the CommandManager. This will mean that these commands work automagically in the majority of situations (where the UI is altered, or the focused element is changed). But in a few cases, such as this one, you will need to manually force the command to re-query. The proper way to do this using this library would be to call the RaiseCanExecuteChanged() method on the RelayCommand.

This is so important and easy to miss, I am repeating what @Samir said in a comment. Mr Laurent Bugnion wrote in his blog:

In WPF 4 and WPF 4.5, however, there is a catch: The CommandManager will stop working after you upgrade MVVM Light to V5. What you will observe is that your UI elements (buttons, etc) will stop getting disabled/enabled when the RelayCommand’s CanExecute delegate returns false.

If you are in a hurry, here is the fix: In any class that uses the RelayCommand, replace the line saying:

using GalaSoft.MvvmLight.Command;

with:

using GalaSoft.MvvmLight.CommandWpf;