What redirect type are you using on your links?
I have the same 404 not found error, I have tried redirection 307, 302 and 301 and it doesn’t work, how can I solve that problem?
You might need to work with your webhost. Pretty Links runs on the plugins_loaded hook to ensure as quick as possible redirect after the plugin is loaded.
Many times this will be caused by a folder in your website directory that has the same name as your link prefix (go, out, or recommends etc).
I don’t have a prefix. They look like normal URL’s. Why do I need to work with my webhost? I just checked the directory, nothing weird. Can you send a email with more info, like site name etc?