There is nothing incorrect about your xs:key definition. Have you properly referenced the XSD in your XML file?
I copied your XML data into a document:
<?xml version="1.0" encoding="utf-8" ?>
<tagSet xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
xsi:noNamespaceSchemaLocation="test.xsd">
<Structure>
<tag>
<name>Steve</name>
</tag>
<tag>
<name>Bob</name>
</tag>
<tag>
<name>Steve</name>
</tag>
</Structure>
</tagSet>
Then I wrote a simple XSD with your xs:key included:
<?xml version="1.0" encoding="utf-8"?>
<xs:schema xmlns:xs="http://www.w3.org/2001/XMLSchema">
<xs:element name="tagSet">
<xs:complexType>
<xs:sequence>
<xs:element name="Structure" type="Structure-type" />
</xs:sequence>
</xs:complexType>
<xs:key name="key">
<xs:selector xpath="Structure/tag" />
<xs:field xpath="name" />
</xs:key>
</xs:element>
<xs:complexType name ="Structure-type">
<xs:sequence>
<xs:element name ="tag" type="tag-type" maxOccurs="unbounded" />
</xs:sequence>
</xs:complexType>
<xs:complexType name="tag-type">
<xs:sequence>
<xs:element name="name" type="xs:string" />
</xs:sequence>
</xs:complexType>
</xs:schema>
And it complains about the duplicate key 'Steve' fine. If this example doesn't help you find the problem, could you post more details about your schema and XML file?