I already knew what I needed to do to fix this problem; I just didn't know how to do it. I was hoping there would be some ready-made tool to do that automatically - but couldn't find any. I am accepting Rod's answer because despite not directly solving my issue, it gives a very good background on the sector size issue, and gave me confidence that the issue really was partition alignment and addressing. For those that come to this question having the same issue, read it thoroughly and carefully, including comments, before doing anything.
In the beginning
I had a computer and needing more space I've bought a new 500GB drive and an USB enclosure. Soon I have noticed that if I partitioned the drive on the enclosure and moved it to the computer, it wouldn't recognize the partitions (and vice-versa). I assumed it was a problem with the enclosure and didn't worry about it.
A wonderful day, my computer decided to not turn on anymore. Turns out the motherboard (unbranded, just a big MADE IN CHINA printed on it) is dead. I've been using it as a file-server and that 500GB drive is now full of data that I can not afford to lose. I am broke now and can not afford a new computer, so my only hope was the "defective" USB enclosure.
Armed with several Linux distributions, a laptop, VirtualBox and the enclosure I did a forensic analysis on the issue. dmesg reported partition size was beyond end-of-drive. So I went through hard drive datasheets, calculated sector counts from scratch, tested drive boundaries manually with dd, and everything looked OK, until I fired up fdisk and it said:
Note: Sector size is 4096 (not 512).
How modest of fdisk. This "note" was the root of all the issues. After some more fiddling these conclusions were drawn:
The USB enclosure is not defective.
The SATA controller on the now dead motherboard is the one that was "weird", at least. It did not report 4096-byte sectors to the operating system, so the OS happily created the MBR using 512-byte sector addresses.
Now when I try to access the partition, the OS tries to use the 512-byte based addresses on a 4096-byte sector drive, and of course, it's not gonna work.
So, how can I correct the addresses in the MBR so they are valid on a 4096-byte sector size, aside from manually editing the MBR on an hex-editor, and
The partitions are not aligned for 4096-byte sectors. There is some tool available to align them aside from copying in and out of another drive? (I do not have spare drives), or will I need to create some tool that "shifts" the data to the side a little chunk at a time? Partitions are ext3.
I found there is a clever way to use dd to shift the partition in-place in this question: How to move a partition in GNU/Linux? But I don't know if it will work on a slice of a sector, though. I can't test it right now but will do when I have some time.
So I have successfully aligned the partition using the method above and hand-edited the MBR on a hex editor. As soon as I re-plugged the HDD, boom partition automatically mounted! I do not recommend this though, there were I/O errors during the process and I could have lost everything, see comment on Rod's answer. For the other partition I will not take risks and will use an old HDD and align chunks at a time by copying the data and then pasting it back on a different position.