I recently did a scaling performance analysis comparing my bitwise tries implementation with red black trees and uthash. If you look at the graphs on http://www.nedprod.com/programs/portable/nedtries/ you'll see how each algorithm scales according to N.
uthash shows very distinct choppiness in scaling - if you test std::unordered_set<> from C++ in an identical framework you get a smooth, flat O(1) line for all operations as one ought to.
In particular you shouldn't be seeing O(1/log N) insert scaling nor O(log N) remove scaling between the bucket expansions as uthash is apparently demonstrating. This suggests that your bucket indexation routine has a bug in it which is introducing the partial log N behaviour, perhaps it isn't making full use of all the buckets for a given hash key?