I've just installed Oblivion GOTY Deluxe using GOG Galaxy. When I try to save the Game selecting New save it tells me the game is saved successfully. If I select Load Game the only game that is available is the Auto-Save. I tried to save over the Auto save and it deleted it. When I looked in \Documents\My Games\Oblivion\Saves I found an Autosave.bak and that was all. Renamed it Autosave.ess and it loaded (about an hour before my last attempt to save).

Tried searching the Discussion but didn't find any similar problems. Is this a GOG Galaxy problem? Not sure I've ever used it to actually install a game before. Should I uninstall and reinstall from my local setup files? Also it's really annoying that GOG Galaxy starts up whenever I Click on the icon to start the game is there anyway to stop that?

Any help would be greatly appreciated.

I don't use Galaxy, so I can't say if the problem is Galaxy-related. Why not download the standalone version ("offline backup game installer") and play this? It definitely doesn't start Galaxy when you launch it.
You might also uninstall Galaxy completely if you don't want to use it.

I have the same problem, the Auto was my only save, saved over the Auto and it deleted my autosave.

What is your operating system and where is your game installed? Sometimes virus protection programs and windows can block saves from actually happening. This sounds like such a case of one of those two happening! If your game is installed into program files, install it somewhere else.

Try to localise the problem:
- Launch Oblivion directly, not via Galaxy.
- Install the direct download version of Oblivion and launch it.
If the problem is still there, move on, otherwise you know it's Galaxy.
- Are you using a save game manager? If yes, disable it, and try again.
- Are you using other mods? If yes, disable them, and try again.
- Like abayarra said: If you installed the game to program files or a subfolder of program files, install it elsewhere, and try again.
- Have a look at the save game folder of Oblivion, should be underneath your user directory in documents\my games\oblivion. Are there any save games the game menu doesn't show you? Is there a subfolder present (shouldn't be there, unless you use a save game manager, or have created it yourself manually).
- I'm not familiar with Galaxy, but if it has cloud-saving features, it might be worth checking, if this is the "culprit". If it's enabled, disable it, and try again.
- Try quick-saving: Does this work?

When the problem survives all these tests, my guess is that there is a conflict between Oblivion and some component of your PC (hardware, software, ...). Can you install Oblivion on a different PC? If yes, try it to see whether or not you can find your saves there.
My personal advice is to never disable any virus-protection software, hoping problems with games might go away. It's unlikely to work, and if it does, chances are that there is something wrong with the game - don't take the risk!