Did you check fuse 10 (15-amp) in the battery junction box or just the ones in the instrument panel fuse box? Fuse 10 is the power to the switched side of the relay. The relay can still switch if that fuse were bad, but battery power would not be provided to the horn. Considering how seldom the horn gets used (unless you use the double press every time you lock the vehicle with the remote to honk the horn) I would be surprised if the relay is faulty.
You could also check for power to terminal 3 of the relay socket and apply battery +12V to terminal 5 of the relay socket to activate the horn.
-Rod