Wine depends on /usr/bin/xmessage which doesn't exist in FC4 - there are unreseolved deps during install via yum. I have looked at the spec file for FC4 and there are 2 Requires for xmessage - %{_bindir}/xmessage and /usr/X11R6/bin/xmessage. The first one should be commented out for FC <=4.
uuuuups... my fault an merging fc5 and fc4 specs...