Perhaps trying format, not just deleting all songs may clear the Genre issue you are seeing, I have yet to see this myself but will keep an eye out for it.

To format, simply right click the device via Explorer and select format.