Oddly enough, the proposed solutions did not work for me. I kept getting
An error occurred (DistributionNotDisabled) when calling the DeleteDistribution operation: The distribution you are trying to delete has not been disabled.
when calling aws cloudfront delete-distribution.
The issue seems to be that you can't immediately disable the distribution with aws cloudfront update-distribution, its status taking a while to be updated (cf. the AWS Console, where the status is shown as 'In Progress').
In summary, the following sequence of commands solved my issue:
aws cloudfront update-distribution
aws cloudfront wait distribution-deployed
aws cloudfront delete-distribution