I ran into this issue when trying to publish a cached map service. I checked my server logs, and the first error message says "Failed setting up the cache folder for the service." I find that if I go into the Cache Folder in Windows explorer where Server is installed (C:\arcgisserver\directories\arcgiscache) and create the folder manually using the exact name that the published server will be, the issue resolved itself. After I created the folder name for the cache in the arcgiscache folder, the issue was fixed.
Perhaps if you created the folder in windows explorer in the arcgisjobs folder it might work as it did for me in the arcgiscache folder.