I used to have the same issue! I was digging all day to find a solution, and at the end (of course) it was very simple!
My w3 total cache troubles were caused by another cashing plugin I installed before! It was this one:
Performance Optimizer Plugin for Wordpress or also called IBinc Performance Optimizer Plugin... I bought it from here - http://codecanyon.net/item/performance-optimizer-plugin-for-wordpress/2413770
After a while, I've decided to add CDN to my blog and I choose to use W3 Total Cache. So I uninstalled IBinc Performance Optimizer Plugin, BUT!!!! One folder left which caused all the trouble! It is in wp-content folder and it called "cache". IBinc was storing all the information about the caching of the pages and the feeds there in files with .dat format! After the De-installation the folder left (the developers should be aware of this issue!) - and the data inside was causing the conflict with w3 total cache!
So I deleted this folder, installed W3 Total Cache (AGAIN!) and.... O! Miracle - it was working!
Conclusion: Be very careful what type of WP plugins are you installing - AND be cautions when you are removing them - trace some footprints they might have left and remove them ASAP!
Hope that helps!