I also hit this issue. I even went as far as downloading the ICS source code. It would seem that the music app on the Nexus is "Google Music", whereas the old music player is "Android Music". The old one is actually included in the source code, but it is not installed as part of the standard image. I actually compiled the old one, and installed it, and when I created playlists there, they were visible to other apps.
I suspect that because "Google Music" can do much more - cloud storage, music store etc. this means that it stores playlists differently. For example, an external app wouldn't know what to do with a playlist which included content which needed to be streamed from Google Music (and probably wouldn't be able to access the service.
I think Google are changing the strategy in the APIs. They now want you to use music controls to play the music in its default player. This makes some sense, but makes it very difficult to support apps which work in <3.0 and >3.0, and will probably become more complicated as more people manually download Google Music.