I am a bit confused here.

A "native vlan" is simply the vlan that carries the untagged traffic. If you are tagging it with the same tag as what the ports native vlan is configured for you are treating the "native vlan" like any other vlan. The client shouldn't know anything about the native vlan.

You can't currently send tagged vlan packets through neutron, at least you can't with OVS. See the relevant code here, OVS is stripping the vlan off the packet before tagging it its own way.

My guess is the linuxbridge plugin works the same way, but I am not positive on that.

What is your overall end goal here?

Yes - with the ML2 plugin and LinuxBridge mechanism driver/agent, this should work. If the Neutron provider network is type VLAN, then the packet will have 2 tags back-to-back (stacked VLANs) when put on the physical switch port, and the switch must support Q-in-Q.

The OVS agent uses VLANs internally to isolate Neutron networks locally. It configures a VLAN for each Neutron network that the node needs to support. This means instances are connected to access ports and OVS will not pass tagged packets it receieves from them - I don't know does if it strips the tags or drops the packet. This blueprint proposal is about adding support for packets tagged on the instance when using the OVS agent.