I have just finished confirming that this problem was indeed caused by some mess up in Gentoo's 32bit filesystem layout (as we discussed on IRC). A solution has been posted: http://wiki.winehq.org/WineOn64bit I am now able to print in Wine using CUPS, not Wine's generic.ppd, again.
Thanks for the input.