Only Global and Universal groups in the same domain as the user can be primary groups for a user. Domain Local Groups cannot be Primary Groups and you can't use a Global/Universal group from Domain A as the primary group for a user in Domain B.  

The storage of primary groups is broken out the way it is because there used to be a fuzzy hard limit on the number of members in a group. If you got above a certain number of members and based on the current memory use on a given DC you could run out of versionstore which would effectively plug up replication. It may unplug itself if you are close to the edge but for really large memberships you could permanently stop replication until the group was trimmed down. That fuzzy limit was ~5000 or so members. Clearly there were many NT4 domains that already had primary groups with more WAY more than 5000 members (the MSFT recommended limit was 40k users, I was personally running one environment with over 80k users in one domain and 60k users in another domain) so they had to come up with an alternate solution - so along came primarygroupid attribute. Windows Server 2003 introduced a new mechanism for storing group memberships (called Linked Values which only works for DN type attributes) and added linked value replication which allowed value level replication for linked attributes (like member) instead of sending the entire group membership every time it changed.    

If making a generic app or script I completely agree that primary group membership should be handled properly. Ignoring it as a large number of publicly available scripts and code snippets do is wrong and cause of issues for companies that actually use alternate primary group memberships.

Depending on the version of the OS you may not be able to search directly for the friendly string format of objectsid. Early on you had to convert it to a blob and send it that way, I think that has been fixed since W2K3 so you generally should be good using it but there is still, unbelievably, a lot of Windows 2000 and even Windows NT out there. The <SID=blah> format is one of two special search base formats available (the other being <GUID=blah> that let you specify something other than a DN for a search base. They require an available global catalog for resolution. See http://msdn.microsoft.com/en-us/library/aa772152(v=vs.85).aspx for more info. 

For the "unwilling to perform" piece, if you can retrieve the extended error info including the DSID that can help understand what is wrong. That is a weird error for that type of request, normally you would expect something like an invalid DN. 

   joe