As I wrote, I already tried the latest Mist wallet. It's the same. Blockchain gets stuck around 3,599,xxx. Havent checked that parity thing, but I assume it's the same.
Apparently there is data missing from your database. This can happen if your PC was shut down abruptly while Geth was in the middle of writing database entries. I don't think there's an easy way our of this, the db is corrupted. You'll have to remove your chaindata
geth removedb
and sync from the start.