Are either [+wf.docid+] or &rowIdPrefix being output by WF in the menu? If the answer is yes, then the problem is not WF...it is in your CSS...
Try this: put the [+wf.docid+] in the li tags, not the anchor tag "a"
Then in your CSS you could have something like
li#15 a {background: url(travel_icon.png) no-repeat center center}
EDIT: As pointed below by Bob, CSS does not accept id values that start with digits
- does it work...?
Was gonna ask if your paths to your images are correct - but you’ve said that it works with your custom tags