I notice that the new version of Papyrus, 0.8.0.v201105250947, now includes Deployment diagrams. A deployment diagram can be created from the tool bar or from the menu (Papyrus perspective) "Papyrus->Diagrams->Create a new Deployment diagram".
However if I right click on model in the Model Explorer view and go to New Diagram, the Deployment Diagram is missing. So too is the Component diagram.
Another issue with the Deployment Diagram is that I cannot create a link between two nodes.