Ok, after beating my head against the wall, reading through the forums, reading the manual for JoomSEF, I finally fixed the issue.
If you install Artio JoomSEF and after editing a URL under "Manage URL's" and then you get 404 page not found, go into the Plugin settings and disable the "System - SEF" plugin. There seems to be a conflict.
Now, I didn't see this anywhere in the manual unless I was looking in the wrong location, but I think this should be one of the main points to be aware of when installing.
My apologies if I overlooked any documentation, but just in case someone else can't find it, hopefully this will help.
argonstudios