You should absolutely be able to multi-thread requests. In fact, this is how clients that work on large batches of leads/activities use the APIs. Have you tried the same code from a single threaded application?
Please feel free to log a ticket if you want someone on our side to take a look