does this happen with all kind of files or with certain extensions only?
also if you're using windows vista.. it could be due to folder permissions/zones.. and maybe because the cache folder is in a high(locked) zone, kmeleon cannot execute the file directly from there.
you'll need to be an administrator on that machine, and change 'elevation' for that folder.
understanding vista's UAC:
http://techrepublic.com.com/2415-10877_11-92761.html
http://www.softblog.com/2008-07/the-first-bug-in-vista-uac/