To clarify: the objectClassCategory for apple-computer, apple-group, and apple-user should be 3; all the other classes should be imported with objectClassCategory set to 1.
Nothing should have an objectClassCategory of 0.
I finally got a chance to test what happens if the apple-computer-list class is added to AD with objectClassCategory: 0, and the results match what you described. When I tried creating a computer list in Workgroup Manager, WGM popped up a dialog with the error "Not authorized. This action failed because you are not authorized to perform the operation.", and the DS debug log had this:
2011-01-22 18:19:57 PST - T\[0xB030B000\] - Client: Workgroup Manage, PID: 63007, API: dsCreateRecord(), Active Directory Used : DAC : Node Ref = 33576284 : Rec Type = dsRecTypeStandard:ComputerLists : Rec Name = Untitled_1
2011-01-22 18:19:57 PST - T\[0xB030B000\] - Active Directory: Using existing connection for example.com - windows-server.example.com. user administrator@EXAMPLE.COM cache MEMORY:wHgljeI
2011-01-22 18:19:57 PST - T\[0xB030B000\] - Active Directory: Add record CN=Untitled_1,CN=Mac OS X,DC=example,DC=com with FAILED - LDAP Error 19
2011-01-22 18:19:57 PST - T\[0xB030B000\] - Client: Workgroup Manage, PID: 63007, API: dsCreateRecord(), Active Directory Used : DAR : Node Ref = 33576284 : Record Ref = 0 : Result code = -14120
2011-01-22 18:19:57 PST - T\[0xB030B000\] - Plug-in call "dsCreateRecord()" failed with error = -14120.
2011-01-22 18:19:57 PST - T\[0xB030B000\] - Port: 27927 Call: dsCreateRecord() == -14120
so having the zero objectClassCategory would account for the problem. Unfortunately, I don't know of any way to change the objectClassCategory once it's set. I hope this happened in a test environment, so you can fix it (set objectClassCategory to 1 for all but the apple-user, apple-group, and apple-computer) before rolling it out to live.
If this did make it to the live domain, there's a workaround: use AD tools (e.g. ADSI Edit) to create apple-computer objects inside the CN=Mac OS X container, then use WorkGroup manager to set them up.
BTW, there's a newer version of the Apple instructions at [http://images.apple.com/business/solutions/it/docs/L407117B-US
Mod_AD_Schema_Support_MacsWP-4.pdf], for Snow Leopard (the one you linked was based on Leopard). The changes aren't terribly important. They removed a bunch of stuff that Snow doesn't use, and added the apple-hwuuid attribute to apple-computer. But the stuff that was removed was hardly ever used under Leopard, and apple-hwuuid isn't actually needed for Snow Leopard, so in fact either set of instructions should work fine with either version of Mac OS X.