I'm not sure if this is a bug or simply a very annoying aspect of this career (giving bad clues on purpose to simulate the actual challenges real police offers have to face). After like 20 false arrests and reloading the game, I've finally made my first arrest.
CLUES: Female, Teen, Long Sleeves Shirt, Skirt, Red Hair, Art Lover
ACTUAL SUSPECT: Male, Young Adult, Brown Hair, Long Pants, Long Sleeves Shirt (at least they got this one right), and probably an art lover as he's with the Avant-Gardes.
So you see, getting all 6 clues has done absolutely nothing for me, and they even got the gender wrong (he doesn't look too androgenous to me).
My best advice would be to follow the clues and try to play the game right at first, but when all else fails - make sure you issue the APB as soon as you arrive at work (as there are less people in the lots in the early morning), and start arresting everyone you see. Eventually, hopefully you'll get your man/woman/whatever. I believe the trait is never wrong, so try getting your sim the Observant trait (500 points). If anyone finds another way, I'm sure all of us would be grateful!