As usual, the first thing to do is check that you have at least the first two hotfixes installed, or better, the first Service Pack (but NOT the last SP).
Max 2012 out of the box (the shipping DVD) has a bug in MAXScript that prevents file creation due to an open/close bug.
Thus, the release version of Max 2012 is not usable with Deadline, Krakatoa or any other Thinkbox product unless the fixes are applied.
If you ARE running an updated version of Max 2012, please let us know.
Also keep in mind that the last SP of Max 2012, as well as Max 2013, also have a change that prevents Deadline from running. So if you see a Service Pack or update released around March-April, DO NOT install it!