There might be an issue with the categorical variables, but most likely the difference between PCA and NMS is happening because PCA has built-in standardizations while NMS does not. Assuming that the variables are on different scales, you might try first relativizing by standard deviates of the variables (i.e. re-expressing each variable as number of standard deviations from the mean). This is what PCA does. Then, in NMS select Euclidean distance.
Btw, either of these makes sense only if the categories are binary or ordered categories. If they are not ordered categorical variables, you should recode them to a series of binary variables.
Also, on the PCA, I recommend not using the broken stick criterion -- it's not nearly as reliable as the randomization test using the eigenvalues.
One other thing... You didn't mention if the NMS was beating the randomization test. A high stress solution would be more acceptable if it beat the randomization test, but at stress=35 I'm doubtful that it would. The randomization test will be slow with that many data points, but if you can run it over a weekend, it would be nice to have that information.
Good luck,
Bruce McCune