Yes, it seems to me that as much of the problem might be fit and your position on the bike rather than the saddle itself.
Go back to the shop and have one of the more senior people examine your position and the way the bike is set up. It may be that a few adjustments will improve things dramatically.