Return to Revisions

Some thoughts in no special order

1. What you've done here might be called extension methods in another language, extending the functionality of the collection class. I would drop the Clx_ prefix and rename the module CollectionExtensions. The callsite would look like If Has(bookCollection, "Great Gatsby") Then ... which is clear enough but you could also qualify with the module name for clarity or intellisense CollectionExtensions.Has
2. That said, removing the Clx_ prefix leaves us with Set, Has, NewKey -one of which is a keyword and the others are quite vague. Maybe consider HasKey, KeyInCollection, since Has could reasonably refer to the value not the key.
3. Has is an implementation detail of NewKey, I would probably inline it, or at the very least make it private, since if you modify the implementation of NewKey so that it no longer requires it, then you'll have to maintain a function in your library you may not need.
4. The performance of NewKey may deteriorate if the caller is setting keys in the same way you are with incrementing values. 4 options: 1) ideally the user can specify a function for generating new keys themselves, but VBA functions can't be passed around so this may be impractical 2) allow the user to specify the seed value so they can avoid most clashes 3) use a GUID which statistically won't have any collisions 4) require a convention -eg reserved value for the temp key. You would have to profile in your usecases.
5. Clx_Set could be renamed and implemented as a property Set/Let

Property Set/Let ItemAtIndex(ByRef clx As Collection, ByVal index As Variant, ByRef value As Variant)

Called like

Set ItemAtIndex(clx, "foo") = obj
ItemAtIndex(clx, "foo") = value 

6. Tests are good, you should test negative position, empty key, null key, key already in collection matching the first candidate for NewKey to ensure that function can handle collisions correctly. I would also use Rubberduck to Assert these things since then you can drop all the debug.print as Rubberduck gives you a graphical representation of the test results, and handles the errors automatically.