Move around and ask other guards. It seemed like there was a range limit on the find command when I played in beta. One guard may not be able to lead me to the person I'm looking for, but the next one down the street could.
Also make darned sure you are spelling the name right, and possibly try just doing the first or last name.
Just a little correction, any guard will help you find an NPC, not just ones with dogs. They have trouble finding people usually in the bigger zones, like North and South Qeynos. I've yet to have them fail me in the suburb zones.
if one guard doesn't know, move to another area of the zone and ask another guard. This will work as long yuou know for certain the NPC is definitly in the zone