Finally some good news today. The auto correct on my Galaxy S4 was totally messed up. It would suggest the corrections in blue near the misspelt word but wouldn't replace it when I pressed space. Instead, the wrong word would be added to 'My word list'. I received a firmware update today which fixed this issue, now the spell correction works fine the way it's supposed to. Of course, the update also retired Latitude on Google maps and moved it to Google+.