I was visiting this forum because I was afraid about "changing" URLs.
handling thus is definitely an option Artio JoomSEF should have:
proposing (through a check box) to handle deleted or renamed urls, to avoid creating duplicate content (bad for google) or "page not found" (bad for users ;-) )

I've not the solution, but maybe a temporary workaround:
Create a custom redirect with your old URL, and redirect to a page with a META-REFRESH set to 5 or something like this, redirecting to your new URL. This hasn't a good reputation, but I believe it's better than a 404 error :-o

Hope it helps you a bit...