So I think I figure out how to make cloud saves to work again.
The problem: The save folder where your progress was supposed to be stored is EMPTY.
Yep, that's right. The GOG Cloud expects to get it's files from C:\Users\{username}\AppData\Local\Necrodancer\saves,
but that folder is always empty, the game never writes data to that folder and so GOG Cloud syncs an empty folder.

So wait where is my save files? The game certainly stores your progress but where?
The Answer: In the C:\Users\{username}\AppData\Roaming\Necrodancer

The Solution: Simply put, just make a symbolic link between the two folders.
How?
First: Open a command prompt (cmd.exe) in Admin mode (we are going for all or nothing here)
Second: Type `cd C:\Users\{username}\AppData\Local\Necrodancer`
Third: Delete that saves folder (it was useless anyway)
Forth: Type on the command prompt `mklink /D .\saves C:\Users\{username}\AppData\Roaming\NecroDancer\`
And Finally: Play the game and let GOG Cloud to do it's magic

A correction Edit: It does save on that folder but it saves the progress of your run and not the unlock progress. The above guide is for keeping also the unlock progress on the Cloud