Create a new space using a keyboard shortcut
OK, using the Automator recording, I made it work with a revised version of the AppleScript in the other answer.

Replace "of group 1" with "of group 2 of group 1 of group 1 of":

on run {input, parameters}

    do shell script "open -a 'Mission Control'"
    delay 0.5
    tell application "System Events" to click (every button whose value of attribute "AXDescription" is "add desktop") of group 2 of group 1 of group 1 of process "Dock"
    delay 0.5
    tell application "System Events" to key code 53

    return input
end run