Um, that should be straight forward. Get a list of the users, query their PrimaryGroupID, store that somewhere (in a hash? :-), see what's in memberOf, get the groupIds of the returned groups and determine the users primary group by comparing their PrimaryGroupId with the groupIds found.

That approach definitely works - I solved the same problem in javascript that way (although I don't have the code anymore).

There could be a maxRows limitation of an LDAP query to AD.

AD defaults to a page size of 1000 objects. You need to use the Net::LDAP::Control::Paged control to handle anything bigger than that. I have code returning tens of thousands of entries from AD on port 389 without a problem that way.