Finally i found the problem.
First, the problem had nothing to do with maximum number of categories or any sort of category limitations. It was a caching bug.
In my specific case, i added 46 terms at once and the plugin created a cache that holds all the children from my taxonomy. Later when i tried to add the 47th term, it was actually added correctly, but the cache was never updated for some reason and it's the reason for all the trouble.
The solution: Clear that cache by deleting the {$taxonomu}_children option.
delete_option("{$taxonomy}_children");