I think a better solution would be to change the way PK titles work, because when it comes to attacking new players, that's generally all people are after. Right now, you get a kill, and it adds one on to your current killstreak, no matter who the individual is. There are two changes I can think of, one simple, and one a little more complicated.
1.) Simply make it so that killing people who have unspecced combat classes doesn't count towards a killstreak.
2.) More complex, but a little more fair... Instead of having just a "killstreak" thing where every kill counts as 1 point, basically, make it more like a meter, similar to the EXP bar, where depending on the player's level relative to your own, you get a different amount of "points". You need varying amounts of these points to get titles (similar to how killstreaks work now), and they reset when you are killed by a player. This would make it so hunting new players has a very low yield titlewise, solving that problem, but it would also make it so level 60's can't get easy titles just off of killing level 15's (specced... not technically new, usually, but still often butchered in a similar way) or other lower levels. It would add a lot more balance to the whole title situation, though it's a little more complicated than the above solution.
I don't really think that track is particularly overpowered, honestly. It's got a pretty long cooldown relative to some skills, so if you're tracking a moving target, you can't just spam it to get their coordinates every two seconds. Only Rangers have it for a guaranteed free price, and while they are powerful, getting attacked by a Ranger isn't quite the same as getting attacked by a DK most of the time. Other classes can still get tracks, but they have to pay for them usually (and if they're after a moving target... they have to buy a lot of tracks.), so that kind of limits it.
It's a useful skill, but I don't really think it's OP. I can understand how it might seem like that when people abuse it on new players like they so often do, but I don't really see why everyone needs to be limited with a nerf on track when only the jerks are the problem. Thus, I think probably the best way to deal with the situation is to take away the reason for them to abuse the skill, and that is to modify how titles work.