The postinst script indeed tries to invoke the restart action, which does not exist for kexec.

Removing the following section from the postinst script seems to fix the problem.

# Automatically added by dh_installinit/13.4.1
if [ "$1" = "configure" ] || [ "$1" = "abort-upgrade" ] || [ "$1" = "abort-deconfigure" ] || [ "$1" = "abort-remove" ] ; then
    if [ -z "${DPKG_ROOT:-}" ] && [ -x "/etc/init.d/kexec" ]; then
        update-rc.d kexec defaults >/dev/null
        invoke-rc.d kexec restart || exit 1
    fi
fi
# End automatically added section
# Automatically added by dh_installinit/13.4.1
if [ "$1" = "configure" ] || [ "$1" = "abort-upgrade" ] || [ "$1" = "abort-deconfigure" ] || [ "$1" = "abort-remove" ] ; then
    if [ -z "${DPKG_ROOT:-}" ] && [ -x "/etc/init.d/kexec-load" ]; then
        update-rc.d kexec-load defaults >/dev/null
        invoke-rc.d kexec-load restart || exit 1
    fi
fi
# End automatically added section

Another deepsea related weirdness: The theme automatically gets added to /etc/default/grub upon installation. This causes grub to complain and wait at boot, if / is encrypted so that the theme files are not accessible.
Idea: Don't modify /etc/default/grub by default, but make it optional by a dpkg question?