To reproduce what I went trhough.
Install clean Kubuntu 12.04.1
Try installing wine. Yes everything looks fine. Cancel it.
Install VirtualBox
Try installing wine, now you can't install it.
Remove all VirtualBox* packages
Wine is installable once more.
Previously I had tried clean installs of Kubuntu 12.04 but I couldn't install wine at all. 12.04.1 may have fixed something.
It is a very confusing issue. I'm sorry to hear it didn't fix it for you. :(
To reproduce what I went trhough.
Install clean Kubuntu 12.04.1
Try installing wine. Yes everything looks fine. Cancel it.
Install VirtualBox
Try installing wine, now you can't install it.
Remove all VirtualBox* packages
Wine is installable once more.
Previously I had tried clean installs of Kubuntu 12.04 but I couldn't install wine at all. 12.04.1 may have fixed something.
It is a very confusing issue. I'm sorry to hear it didn't fix it for you. :(