I am experiencing a really weird issue: When I modify a product URL key in backend, redirect from old URL doesn't apply. Valid URL is still the old one, in spite of new one is shown in backend. If i type in my browser the new URL, i get 404 error.
Have you changed the URL in the correct Current Configuration Scope? This only applies if you run a multi-store.
More on Configuration Scope: http://docs.magento.com/m1/ce/user_guide/configuration/scope.html
Seems like the URL index is not updated yet. Go to System > Index Management, select the catalog URL rewrite index and then select "refresh" from the actions menu.