The game will not work in full screen (works in virtual desktop) from cd or dvd, maybe the steam version does. Anyway just change the setting from full screen to emulate a virtual desktop. This will work with Heroes of might and magic V version 1.6. When updating use patch 1.4 then 1.41 then 1.5 and lastly 1.6. If you try to update to 1.6 first it wont work. It will also work with tribes of the east. However, tribes of the east will not update properly. It tells you it will but it won't. The official updated version is 3.1 not 3.0 The status for this game should be silver not gold. Just so you know the game is very much playable.
To emulate a virtual desktop go to configure (at the top of your screen), click manage bottle, click on control panel (make sure you have the bottle that you installed the game on selected), scroll down to winecfg and launch selected item, click on the graphics tap, check the box that says emulate virtual desktop, apply or click ok. Now it will work. You can change the screen resolution of the virtual desktop. I use 1024-768 rather than the 800-600.
Hope this works for everyone.