Using Bulk API in concurrent fashion (multiple jobs running at the same time) is the fastest option. If you use Salesforce Data Loader, it will create multiple Bulk API requests/jobs and fire them in parallel for you (see BulkAPI vs Dataloader? for details). To improve throughput, you can request a temporary increase in API limits.
Salesforce has a limit on the number of updates you can make to the same record in a single batch. Similar issue in this thread: https://success.salesforce.com/answers?id=9063A000000pHMKQA2
The limit is 12 in each batch of 200.
Workaround for this is to set your batch size lower, likely down to 12 to avoid the issue completely.
A better fix would be to ...
We have the Professional Version of Salesforce right now, and a lot of the options shown haven't been working for us either because they're only available in Enterprise and up, or we aren't good enough at Salesforce yet. This app, however, did work for us and it was free :)