Windows had changed the HD partition map from GUID Partition Table(GPD) to MBR. And made HD a "dynamic disk". This is why Mac Os wasn't able to boot. 

So, I've tried 1001 ways to recover. Nothing worked. Interned Recovery gives -2002F error. Macbook pro 2012 can't boot from bootable DVD to use DiskWarrior, Drive Genius or similar. It can't boot from OS X Lion install DVD. I could boot Windows recovery console and tried TestDisk which failed to write something to HFS+. Also tried some Windows third party applications which also failed. 
 
**I asked a friend with latest Mavericks(which I had too) to make a Recovery USB using [OS X Recovery Disk Assistant v1.0][1] and make a DMG file from it using Disk Utility and send me over internet. Then I used the [TransMac][2] application under Windows and burned DMG on my USB stick. I was able to boot from this USB stick into Recovery Mode and from there I can reinstall Mac Os X Mavericks. Somehow it sees my Ethernet cable and doesn't give error.**
 
Note: that Disk Utility wasn't able to recover partitions. I tried to run DiskWarrior from terminal but it gave me an error. TestDisk didn't run too. I could recover or backup my files using [Paragon Rescue Kit for Mac Bootable CD][3], but there was no need since it's my new macbook and I didn't have much files there. I made a clean installation on a USB stick and run DiskWarrior and Drive Genius, none of them could fix partitions. So I gave up and reformatted HD. 

That's probably not the answer on how to fix partitions, but that's how I solved this. If somebody finds a way to fix partitions please post as an answer. 

  [1]: http://support.apple.com/kb/DL1433
  [2]: http://www.acutesystems.com/scrtm.htm
  [3]: http://www.paragon-software.com/home/rk-mac/