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.

Thanks for writing this up. Bookmarking it — the kind of thing I will want to reference again in a month.