[Plugin: WP Super Cache] Error Message on After a Move to New Server

I used to use WP Super Cache for several years. Few days ago I moved onto a different dedicated server with different host and have been completely unable to get the plugin to work. The error I get is:

Your cache directory () did not exist and couldn’t be created by the web server. Check permissions.
Cannot continue… fix previous problems and retry

Since I’ve been trying to get this resolved for days and spent lots of money on server techs who said they would resolve it but none did, I found that the way to by pass this error is by manually creating the /cache/ subdirectory in wp-config directory. That eliminates the error message, however caching still does not work. Files are created inside the folder, but none of the folder tree for each of the categories and posts within it are created. As a result, when I go to the Contests tab of the plugin settings, it constantly shows that 0 pages are cached and/or supercached (even after regeneration of stats).

Similarly, testing the cache on Easy tab returns a message that time stamps either could not be read or did not match. I’ve run out of all of my options and the last resort was to ask for help here. If I’m unable to resolve it, I’ll have to give different caching plugin a try cause my DB server is getting hammered (it’s a very high traffic blog I run). Anyone able and willing to offer input as to what I can do to get WP Super Cache to work?

Thank you :/

http://wordpress.org/extend/plugins/wp-super-cache/