I tried it twice, first on an NPC (a Wood Wailer Sentry FATE helper) and then on an actual player in Thanalan, both of which self-targeted. The player may have been doing some sort of quest, guildleve or levequest but if I remember correctly, you can heal players who are doing those, you just can't attack their special targets.

After finding out the self-targeting behavior from some online sites, I tried casting Protect on another player again, this time much closer and it worked.