Just to be sure, did you try it on the same PC but with different OSs or were you using different PCs?
Did you make sure to be using 2.0 USB ports? Some issues are known to be caused by 3.0 USB ports, most of the times this shouldn't be an issue, however you could try it.
When you connect your Galileo to the power supply do you see any LED activity? If so, could you connect your Galileo with the serial cable? Does it appear on your device manager as USB Serial Port? If it does, try to connect to the Galileo's Linux terminal. Does it show any error message? Is there any strange activity? Is the board constantly rebooting? Or are you able to access the terminal as expected?
When connected to Power Supply, boots up as it should. When connected via USB, nothing happens. When connected serially, it does get recognized.