Same problem here. When the built in prestashop smarty cache is enabled, and the blocklayered module us used on frontend for color filtering, the small color boxes are not shown or are showed randomly in the product list. I also have third party pagecache module, with that there is no problem. But if I turn off prestashop smarty cache the admin is slow, so this is not the proper solution.
The problem appeared after updating from 1.6.0.14 to 1.6.1.1 and is still there in 1.6.1.2.