The solution was that the Cassandra page for installing from deb wasn't very clear to me:
Alternatively, you can install directly from the ASF repositories:
deb http://www.apache.org/dist/cassandra/debian 11x main
deb-src http://www.apache.org/dist/cassandra/debian 11x main
You will want to replace 11x by the series you want to use: `10x for the 1.0.x series, 08x for the 0.8.x series, etc... You will not automatically get major version updates unless you change the series, but that is a feature.
As it had 11x in the documentation I assumed that was the latest version rather than 20x as it should have been, then everything worked.