Are you behind a caching proxy server?
Are you using cache duration > 0 in feature settings?
Are you running low on disk space?
Are you seeing any errors in the log about file permission errors? We clear the cache by touching certain files, if it can;t modify the file it would fail to clear the cache.