Firstly, are you using shadow dom or the (default) shady dom? I guess the latter - iinm, with shady dom (and with the polyfill on Polymer 0.5) the css actually ends up in the main html head (after some modification to make it specific to the element it is declared in and other stuff). So, it's plausible that you could add it in the main html head after prepending the element name manually to each rule; but that probably isn't a good idea since it'll break when Polymer stops using the polyfill by default (ie when the features are supported cross-browser ... who knows when that will be). However, it might be worth trying as a debug step or as a matter of interest or something like that.
I think the real solution is probably to use this.updateStyles() after loading the style as described below - I don't see you mentioning that, so I'm not sure if you have tried it or not :
I'm not sure if that would work or not, but it's worth a try. You might also try to load the stylesheet by ajax and create a <style> element instead of a <link> element, and then append that to your element - I think I tried something like this in Polymer 0.5 (to get around the deprecation of /deep/ and ::shadow in stylesheets), and seem to recall it working ok...ah, found it, yeah, this is what I ended up with :
var theGraphStyle = document.createElement('style');
theGraphStyle.textContent = '@import "css/slv-the-graph.css";';
editor.$.editor.$.graph.shadowRoot.appendChild(theGraphStyle);
(You'll probably want to replace 'editor.$.editor.$graph' with simply this.shadowRoot). But, remember, that was with Polymer 0.5, and I'm a bit 'green' with 1.0, so YMMV, but at least some things to try.
HTH.
Max.