Exclusion constraint for text values

I have two tables. A client table and a vehicle table, the two are linked in a unit lookup table. My constraint is that a vehicle cannot belong to a client if it already is associated with another client. This is what I have so far:

ALTER TABLE unit 
   ADD CONSTRAINT unit_vehicle_across_client_constraint 
   EXCLUDE USING GIST (client WITH =, vehicle WITH ) DEFERRABLE;

But it doesn't seem to work. I guess I just don't really understand how the exclusion parameters really work. Any suggestions?