Yup that has been checked from the beginning. I'll check out the wifi syncing thread 
What path do you have set for playlists for that device and do the playlist files actually get transferred to the device to the matching folder?
That will at least indicate if it's a problem with the sync or a problem with the player on the device picking up the playlists.
edit: If you set to the playlist folder so it's inside your music folder, the apps will probably pick up the playlists no problem but if you have it set to outside the music folder, you will need to let the app know where to find them.
My device has the following settings
storage path - 23049PCD8G\Internal shared storage\
playlist path - Music\Playlists\
If your playlist path is set to just "Playlists", the music app won't find them unless you add 23049PCD8G\Internal shared storage\Playlists as a folder for it to look at. Obviously your device name will be different (probably).