If you upgrade to AutoNav 1.5.0, you must go through the AutoNav settings screen and set the tag category to "media-tags" (without the quotes). AutoNav now supports arbitrary values for the postid="tag:" and postid="category:" selections for attachments.
Also, you can now select attachments from any post or page using:
[autonav display="attached" postid="-1,tag:dessert" orderby="rand" count="6"]
which would display a gallery of six images, randomly chosen from all the attachments (regardless of their parent post or page) and tagged with the "dessert" tag with the Media Tags plugin.