O right. From the conversation on IRC I got the impression the issue was the application calling the device's Release before calling the surface's Release. Similar to the Surface / Texture issue. On windows that should work, on wine it will probably fail at the moment.
Releasing the device after all its children are deleted should work though, and it might simply be a matter of the object (be it a surface or something else) not releasing its references to the device properly upon deletion.
I also suspect there might be a couple of circular references in the form of device->stateblock->object->device, but I haven't had time to really look into that yet. I *think* wined3d shouldn't keep references to objects in the device's Set* methods, but I remember that when I removed them in IWineD3DDeviceImpl_SetVertexShader Oliver put them back again in a later patch for some reason.