Is it possible to change navigation for an AI character during gameplay?

Okay, I can confirm that issue that appears in 4.1.1 is fixed in 4.3.1. If at all possible, I would recommend upgrading and then making a copy conversion of your project, making sure settings are same as listed above, and see if you run into same problem. There were a fair amount of improvements with Navigation and Behavior Tree systems with last few updates, and you might run into fewer problems.

Hope that helps!