To explain this better, here's an example of what was happening:
Putting in a date like '9/4/14' should make the spreadsheet show it as '9th April 2014', instead it was being shown as '4th September 2014'. This is because the US and Australian date formats swap the month and day around. This was making each of the dates I put in out of whack or they were simply not being picked up as valid dates.
The solution is quite simple.
To fix this for good, you need to update the Language for your Google profile by selecting Australia as the Language Variant. For some reason mine was set to United States, and that was causing my dates to go crazy.
Now the above setting will only affect new spreadsheets you make, so to fix your existing spreadsheet, you need to update the settings on that spreadsheet itself. This is found in the File menu when the spreadsheet is open.
Change the locale to Australia.
What I found interesting is that the existing dates are transformed to be in the new format, so my original '9/4/14' entry got changed to '4/9/14' to match the new locale, this is great! Entering new dates now the spreadsheet treats them the way I wanted to in the first place.