When creating new users with the Hybrid Provider, (or really any custom Membership Provider) you'll need to pass a valid "ProviderUserKey." This is essentially the "primary key" of the user (in database terms, if you will).
So I was passing Guid.NewGuid().ToString() to HybridProvider.CreateUser at my client, and ASP.NET kept giving me InvalidProviderUserKey errors. Something you need to look out for is not only to pass an unused value for this parameter (since it is a unique key; "DuplicateProviderUserKey" is a different exception), but also that the object you pass needs to be of the correct type specific to the current user data store!
For example, if you are querying AD, this is the SID of the user. In SQL, its the UserId. Same idea, different data types. That's why this parameter of this method is of type System.Object. If you are talking to AD, you need to pass a byte array (this is unconfirmed; I'm too afraid to programmatically create users in AD...it just feels morally wrong, like I'm genetically creating people via .NET code). If you're talking to SQL, this needs to be a Guid.
So all I had to do was change Guid.NewGuid().ToString() to Guid.NewGuid() and it worked! Removing ToString to get past this issue has just undone the years of physiological development I went through when I converted myself from VB to C#, but it sure beats the years of therapy I would have needed if I couldn't create users with my own membership provider!