I am the webmaster at Valdosta State University in Georgia. We had the same problem with our setup. In the end, after trying several different ideas, we ended up setting up a secondary LDAP server that populates from our Sun system and bouncing CPS off that for authentication.
SOLUTION! Sounds like CPS tries to search or wildcard for group info, even though it is optional. So if you have the group info filled out, even if you don't use it, it seems to speed up drastically. Entering the group search info makes authentication take seconds from 5 or so minutes.
I added the attributes in on the Group Search tab and voila! Thanks for the info.
How nice to see that even in 2006 Adobe doesn't support it's own products and refers customers to go look on the forums so that other customers can help solve the problem for them.
It's a good thing their company doesn't make it's revenue off support since the only thing their support staff is good at is finding ways not to give support.
I had a similar issue and am now able to authenticate very fast. The search still seems to be dreadfully slow (I'm assuming because of all the wildcarding). It takes forever to add them to a website through contribute because I have to search for each person, which is the same as the "User and Group Search Test" in the admin console.
Any suggestions on how to speed this up or do we really need to wait for the next CPS update (which could be years). PS, I have already filled out the Group Search Criteria.