Couple of quick corrections.
Primary Groups are in Windows for UNIX/POSIX type use; it had nothing to do with hybrid NT/AD domains. Windows nor Windows NT really didn't care about that value; 99%+ Windows environments that I have seen (literally thousands) the primarygroup ID is Domain Users with a smattering of Domain Admins. Companies (usually larger companies) that had UNIX apps bumping up against Windows file servers or apps ported to Windows from UNIX would make use of the primarygroup and those companies would switch the values up as needed. SFU later added in a Primary Group Name / GID attribute to AD to use for UNIX integration.
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.
[Fri 04/11/2014 20:15:34.38] C:\temp>adfind -b "<SID=S-1-5-21-2219134293-820887505-3664443653-513>" -s base member
AdFind V01.47.00cpp Joe Richards (joe@joeware.net) October 2012
Using server: TestADI-DC1.testadi.loc:389 Directory: Windows Server 2003
dn:CN=Domain Users,CN=Users,DC=testadi,DC=loc
member: CN=testblah,CN=Users,DC=testadi,DC=loc member: CN=Administrator,CN=Users,DC=testadi,DC=loc
1 Objects returned
[Fri 04/11/2014 20:15:37.70] C:\temp>adfind -b "<SID=S-1-5-21-2219134293-820887505-3664443653->" -s base member -exterr
AdFind V01.47.00cpp Joe Richards (joe@joeware.net) October 2012
Using server: TestADI-DC1.testadi.loc:389 Directory: Windows Server 2003
ldap_get_next_page_s: [TestADI-DC1.testadi.loc] Error 0x22 (34) - Invalid DN Syntax
Extended Error: 0000208F: LdapErr: DSID-0C090654, comment: Error processing name, data 0, vece
0 Objects returned
joe