IT WORKED!
Thank you so very very much, you're my hero. I will be playing this game A LOT thanks to you.
Best technical support I have ever needed.
You're the best.

The game didn't open when changing the memory settings so I tried the command you told me. One of the lines was this one:
Picked up _JAVA_OPTIONS: -Xmx512M
I understand that I'm limitting the memory usage of java but I don't know how to change it.
I tried this command on the cmd:
java -Xmx4096m
But it changed nothing.
Sorry if I'm missing out something very obvious here.

Tried what you told me to and the game didn't open when pressing "start game" on the old launcher. Downloaded the Beta Launcher and this time it did open, but the same thing as before happened, got stuck at "connecting to universe". Noticed on the log that this time it said that it was running on 64 bit java and that the game was installed on c:\starmade, but it says that my OS is windows 8.1 which didn't happen before.