This message of "Jenkins doesn't have label XXXX" is rather misleading and unhelpful.
You think the problem is something you did wrong in your configuration and when you find out what happen it is nothing to do with jenkins or how you set up the docker plugin.
I run into the same problem than you, and the problem was the docker installation I was using.
The steps I followed to fix it were:
(I was using CENTOS7,jenkins 2.1.38, docker version 1.13.1)
1) Go to the logs of your jenkins (centos logs are /var/log/jenkins.log)
2) Looking into the logs you are going to find out the problem. For instance for me was this:
com.github.dockerjava.api.exception.NotFoundException: {"message":"driver failed programming external connectivity on endpoint happy_heyrovsky (cbfa0d43f8c89d2531323249468503be11e9dd603597a870530d28540c662695): exec: \"docker-proxy\": executable file not found in $PATH"}
As you see the problem is that docker it is not able to find docker-proxy ¿how to fix this?
Go to /usr/libexec/docker and you will see docker-proxy-current. so what you have to do is create a link:
sudo ln -s docker-proxy-current docker-proxy
Tha´s all. After doing this change I execute my build on jenkins and it works.