Run wp jetonomy flush-rules (or visit Settings > Permalinks and save) after changing the base slug. The 404s are stale rewrite rules — regenerating them fixes it immediately.

Could you say more about how you measured the result? I want to try this but I am not sure what success would look like.