So working with ESRI they are able to replicate the behavior, and are encountering similar behavior when trying to use a proxy instead as I tried.
I have 2 other 3.1 applications which I have not upgraded (good thing) and they contain GP services secured in the same location and with identical permissions as the one I'm trying to use in 3.2, and they work perfectly.
This is starting to look like a 3.2 issue.
I also tried to add the other 'working' GP service which is used in the 3.1 app to the 3.2 app and I'm prompted for credentials; every time I submit the credentials the sign-in just keeps popping up again. When both GP services are exposed in the viewer app, one prompts for credentials, the other says 'Could not determine geoprocessing execution type' (as it did before when I tried to use the proxy).
So back to Bjorn's observation, I do believe that the other issue and this are indeed related. While for some reason the 2 GP services behave differently when executed, it appears that credentials are not being passed correctly.