moby: "shim error: invalid argument" when trying to run a container after upgrading to v1.11

Output of docker version:

Client:
 Version:      1.11.0
 API version:  1.23
 Go version:   go1.5.4
 Git commit:   4dc5990
 Built:        Wed Apr 13 18:17:17 2016
 OS/Arch:      linux/amd64

Server:
 Version:      1.11.0
 API version:  1.23
 Go version:   go1.5.4
 Git commit:   4dc5990
 Built:        Wed Apr 13 18:17:17 2016
 OS/Arch:      linux/amd64

Output of docker info:

Containers: 5
 Running: 0
 Paused: 0
 Stopped: 5
Images: 1
Server Version: 1.11.0
Storage Driver: aufs
 Root Dir: /var/lib/docker/aufs
 Backing Filesystem: extfs
 Dirs: 12
 Dirperm1 Supported: false
Logging Driver: json-file
Cgroup Driver: cgroupfs
Plugins:
 Volume: local
 Network: bridge null host
Kernel Version: 3.2.0-4-amd64
Operating System: Debian GNU/Linux 8 (jessie)
OSType: linux
Architecture: x86_64
CPUs: 4
Total Memory: 17.68 GiB
Name: d1
ID: DRUU:7R2I:CVOG:RAS5:UI73:ZI54:DARD:YUU7:GII2:JBMT:ANCS:G4VR
Docker Root Dir: /var/lib/docker
Debug mode (client): false
Debug mode (server): false
Registry: https://index.docker.io/v1/
WARNING: No memory limit support
WARNING: No swap limit support
WARNING: No kernel memory limit support
WARNING: No oom kill disable support
WARNING: No cpu cfs quota support
WARNING: No cpu cfs period support

Steps to reproduce the issue:

1. Upgrade v1.10 to v1.11 on Debian Jessie (Linux 3.2.0-4-amd64 #1 SMP Debian 3.2.73-2+deb7u2 x86_64 GNU/Linux).
2. Execute docker run hello-world

Describe the results you received:

$ docker -D run hello-world
DEBU[0000] Corrupted prefix: []
DEBU[0000] [hijack] End of stdout
docker: Error response from daemon: rpc error: code = 2 desc = "shim error: invalid argument".

daemon.log:

Apr 14 14:55:28 d1 systemd-udevd[4008]: failed to execute '/lib/udev/socket:@/org/freedesktop/hal/udev_event' 'socket:@/org/freedesktop/hal/udev_event': No such file or directory
Apr 14 14:55:28 d1 systemd-udevd[4010]: failed to execute '/lib/udev/socket:@/org/freedesktop/hal/udev_event' 'socket:@/org/freedesktop/hal/udev_event': No such file or directory
Apr 14 14:55:28 d1 systemd-udevd[4018]: failed to execute '/lib/udev/socket:@/org/freedesktop/hal/udev_event' 'socket:@/org/freedesktop/hal/udev_event': No such file or directory
Apr 14 14:55:28 d1 systemd-udevd[4016]: failed to execute '/lib/udev/socket:@/org/freedesktop/hal/udev_event' 'socket:@/org/freedesktop/hal/udev_event': No such file or directory
Apr 14 14:55:28 d1 systemd-udevd[4019]: failed to execute '/lib/udev/socket:@/org/freedesktop/hal/udev_event' 'socket:@/org/freedesktop/hal/udev_event': No such file or directory
Apr 14 14:55:28 d1 systemd-udevd[4020]: failed to execute '/lib/udev/socket:@/org/freedesktop/hal/udev_event' 'socket:@/org/freedesktop/hal/udev_event': No such file or directory
Apr 14 14:55:28 d1 docker[3196]: time="2016-04-14T14:55:28+02:00" level=error msg="containerd: start container" error="shim error: invalid argument" id=9c17448db69fc62c68dc09fb6c52437a2faa8d01ba8c6018ee17dbe24734a303
Apr 14 14:55:28 d1 systemd-udevd[4033]: failed to execute '/lib/udev/socket:@/org/freedesktop/hal/udev_event' 'socket:@/org/freedesktop/hal/udev_event': No such file or directory
Apr 14 14:55:28 d1 systemd-udevd[4034]: failed to execute '/lib/udev/socket:@/org/freedesktop/hal/udev_event' 'socket:@/org/freedesktop/hal/udev_event': No such file or directory
Apr 14 14:55:28 d1 systemd-udevd[4036]: failed to execute '/lib/udev/socket:@/org/freedesktop/hal/udev_event' 'socket:@/org/freedesktop/hal/udev_event': No such file or directory
Apr 14 14:55:28 d1 systemd-udevd[4037]: failed to execute '/lib/udev/socket:@/org/freedesktop/hal/udev_event' 'socket:@/org/freedesktop/hal/udev_event': No such file or directory
Apr 14 14:55:28 d1 systemd-udevd[4040]: failed to execute '/lib/udev/socket:@/org/freedesktop/hal/udev_event' 'socket:@/org/freedesktop/hal/udev_event': No such file or directory
Apr 14 14:55:28 d1 systemd-udevd[4042]: failed to execute '/lib/udev/socket:@/org/freedesktop/hal/udev_event' 'socket:@/org/freedesktop/hal/udev_event': No such file or directory
Apr 14 14:55:29 d1 docker[3196]: time="2016-04-14T14:55:29.095680354+02:00" level=error msg="Handler for POST /v1.23/containers/9c17448db69fc62c68dc09fb6c52437a2faa8d01ba8c6018ee17dbe24734a303/start returned error: rpc error: code = 2 desc = \"shim error: invalid argument\""
Apr 14 14:55:37 d1 ntpd_intres[1893]: ntp_intres.request: permission denied
Apr 14 14:55:37 d1 ntpd_intres[1893]: ntp_intres.request: permission denied

Describe the results you expected: The hello-world text is displayed.

Additional info: I’m assuming this is not a general Debian Jessie issue, but purging/reinstalling Docker has not helped. Building an image fails with the same message after pulling the layers.