Background Manager has been tested with WP Super Cache, W3 Total Cache as well as the third party service CloudFlare (as used on the BGM Demo Site).
Also keep in mind that garbage collection will need to be done at 12 hours or less, due to the default setting of NONCE lifetimes within WordPress (24 hours, set in 12-hour blocks - more details here: http://myatus.com/p/wordpress-caching-and-nonce-lifespan/ ).
Background Manager will also automatically utilize PHP APC, if it is installed, which can increase its performance. You can check if it is enabled by going to the main Settings page (Appearance -> Background) and clicking the Debug link at the bottom of said page. You would see:
Pf4wp APC Enabled: Yes
Further improvements based on APC and Memcache(d) are on its way.