Do I have duplicate key indexes?
object_id is indexed three times

PRIMARY KEY
UNIQUE KEY link
FOREIGN KEY fk_object

object_term is actually indexed once

fk_term
In UNIQUE KEY link, object_term is not the lead column.

UPDATE 2011-12-09 19:42 EDT
In the First try:

object_id is unique (PRIMARY KEY)
(object_id,object_term) is unique (this means object_id can only be associated with one object_term at any given moment)

In the Second try:

object_id is not unique
(object_id,object_term) is unique (this means object_id can only be associated with more than object_term)

UPDATE 2011-12-09 19:57 EDT
If you are concerned about diskspace taken by indexes, you have a decision to make
OPTION 1 : Diskspace is no object
This can only be beneficial if your queries effectively use covering indexes and you are willing to live with (and provide for) large diskspace.
OPTION 2 : Diskspace is a precious commodity
It's time to do some forecasting. Both object_id and object_term are BIGINT. You can cut space down some as follows:
SELECT * FROM relations PROCEDURE ANALYSE();

This will not dump all the rows. It will sample the data and come back with a recommedation for the best column definitions given the data.
Why is that important?

TINYINT UNSIGNED is one byte (Range 0 to 255)
SMALLINT UNSIGNED is two bytes (Range 0 to 65535)
MEDIUMINT UNSIGNED is three bytes (Range 0 to 16777215)
INT UNSIGNED is four bytes (Range 0 to 4294967295)
BIGINT UNSIGNED is five bytes (Range 0 to 2^40 - 1)

If you know the number will not surpass certain values, you can change the column definitions to accommodate less diskspace. At the very least, let PROCEDURE ANALYSE() suggest it for you.
OPTION 3 : Diskspace can be a bottleneck
The more house guests, the more housekeeping to accommodate. If a host can take care of 20 house guests, keep them all 20 happy, and the host is happy as well, the host can always care 20 house guests over and over again. Add one more guest, and the host's quality of services goes down hill. The same goes with indexes. If your queries are fast enough to warrant keeping indexes around, you need to select which indexes are really necessary, and eliminate indexes that are redundant (unwanted house guests). The host must make sure the each house guest's request (query) can be satisfied (done with covering indexes)
Nice Links on Covering Indexes

http://peter-zaitsev.livejournal.com/6949.html
http://www.mysqlperformanceblog.com/2006/11/23/covering-index-and-prefix-indexes/
http://ronaldbradford.com/blog/tag/covering-index/