Parallel bzip2: lbzip2
As follow up to a previous post: Splitting a big file with split.
If the speed is limited by the bzip2 process this can be parallelized by using: lbzip2.
Lbzip2 works as a drop-in replacement to bzip2. All distributions should have a package for lbzip2.