Are you using relative links in your Redirects, e.g. “/apex/skuid__UI?page=NewApplication&id=a0600000000123”, as opposed to absolute links, e.g. “https://skuid--acme--full.na12.visual.force.com/apex/skuid__UI?page=NewApplication&id=a060000000000123”?
