Changing the cursor in WPF sometimes works, sometimes doesn't

Do you need the cursor to be a "wait" cursor only when it's over that particular page/usercontrol? If not, I'd suggest using Mouse.OverrideCursor:

Mouse.OverrideCursor = Cursors.Wait;
try
{
    // do stuff
}
finally
{
    Mouse.OverrideCursor = null;
}

This overrides the cursor for your application rather than just for a part of its UI, so the problem you're describing goes away.

One way we do this in our application is using IDisposable and then with using(){} blocks to ensure the cursor is reset when done.

public class OverrideCursor : IDisposable
{

  public OverrideCursor(Cursor changeToCursor)
  {
    Mouse.OverrideCursor = changeToCursor;
  }

  #region IDisposable Members

  public void Dispose()
  {
    Mouse.OverrideCursor = null;
  }

  #endregion
}

and then in your code:

using (OverrideCursor cursor = new OverrideCursor(Cursors.Wait))
{
  // Do work...
}

The override will end when either: the end of the using statement is reached or; if an exception is thrown and control leaves the statement block before the end of the statement.

Update

To prevent the cursor flickering you can do:

public class OverrideCursor : IDisposable
{
  static Stack<Cursor> s_Stack = new Stack<Cursor>();

  public OverrideCursor(Cursor changeToCursor)
  {
    s_Stack.Push(changeToCursor);

    if (Mouse.OverrideCursor != changeToCursor)
      Mouse.OverrideCursor = changeToCursor;
  }

  public void Dispose()
  {
    s_Stack.Pop();

    Cursor cursor = s_Stack.Count > 0 ? s_Stack.Peek() : null;

    if (cursor != Mouse.OverrideCursor)
      Mouse.OverrideCursor = cursor;
  }

}

You can use a data trigger (with a view model) on the button to enable a wait cursor.

<Button x:Name="NextButton"
        Content="Go"
        Command="{Binding GoCommand }">
    <Button.Style>
         <Style TargetType="{x:Type Button}">
             <Setter Property="Cursor" Value="Arrow"/>
             <Style.Triggers>
                 <DataTrigger Binding="{Binding Path=IsWorking}" Value="True">
                     <Setter Property="Cursor" Value="Wait"/>
                 </DataTrigger>
             </Style.Triggers>
         </Style>
    </Button.Style>
</Button>

Here is the code from the view-model:

public class MainViewModel : ViewModelBase
{
   // most code removed for this example

   public MainViewModel()
   {
      GoCommand = new DelegateCommand<object>(OnGoCommand, CanGoCommand);
   }

   // flag used by data binding trigger
   private bool _isWorking = false;
   public bool IsWorking
   {
      get { return _isWorking; }
      set
      {
         _isWorking = value;
         OnPropertyChanged("IsWorking");
      }
   }

   // button click event gets processed here
   public ICommand GoCommand { get; private set; }
   private void OnGoCommand(object obj)
   {
      if ( _selectedCustomer != null )
      {
         // wait cursor ON
         IsWorking = true;
         _ds = OrdersManager.LoadToDataSet(_selectedCustomer.ID);
         OnPropertyChanged("GridData");

         // wait cursor off
         IsWorking = false;
      }
   }
}