MySQL Question - Unique Key Not functioning correctly, or am I misunderstanding?

The only way I can think of handling this without additional triggers/programming would be to have a single "None of the Above" value in each of the referenced tables, so that your test would look like

INSERT INTO test VALUES (1, NO_LOCATION, NO_WORKGROUP, NO_PROGRAM),
                        (1, NO_LOCATION, NO_WORKGROUP, NO_PROGRAM)

Where the NO_* identifiers are the right type/length for your ID columns. This would then fail, as you'd expect it.

This is a Feature (though not what I expected, either).

This thread suggests making your key a Primary key to get the behavior you expected:

This is a feature - a NULL value is an undefined value, therefore two NULL values are not the same. Can be a little confusing but makes sense when you think about it.

A UNIQUE index does ensure that non-NULL values are unique; you could specify that your column not accept NULL values.