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.