I realize this question was asked 6 months ago, I hope you've already found the solution. I'm posting the answer here for future reference.
You were almost there. Removing the existing symlink is the correct first step. The next step is to create the new symlink by doing:
ln -s [actual/path/to/cabal] [name_of_symlink]
You seem to have reversed this order, and this causes the "File Exists" error.