The headline describes the problem but a few more details…
URL redirect does not help domain.com/blogs/[category-handle]/[old-handle] > domain.com/blogs/[category-handle]/[new-handle]
Changing the URL before saving does not help either domain.com/blogs/[category-handle]/[new-handle-before-saving]
When doing the same thing on a test blog post it works, does that mean that specific slug is taken already? domain.com/blogs/[category-handle]/[test-handle] + Redirect both work