Turns out it was the starter motor. They guys at the local servo took it out but couldn't fix it so they had to replace it. $500 later we have a working car again.
The problem with owning a new car or motorbike is that the insurance and rego coincide. So each year you get a bunch of bills that all happen at the same time.... this just happened with my bike. Coupled with the recent car problems, I've spent over $2000 on the VISA in the last day and I've got nothing to show of it. Snuh.