Inconsistent select count and select distinct

When performing select count( * ) from ... I expect the results to be consistent over multiple query executions if the table at hand is not written to / deleted from in the mean time. However, in my set-up it is not. The counts returned vary considerable (several percent). The same holds for select distinct partition-key-columns from ....

I have a table in a keyspace with replication_factor = 1 which is something like:

CREATE TABLE tbl (
    id frozen<id_type>,
    bucket bigint,
    offset int,
    value double,
    PRIMARY KEY ((id, bucket), offset)
)

The frozen udt is:

CREATE TYPE id_type (
    tags map<text, text>
);

The table contains around 35k rows (I'm not trying to be funny here ...). The consistency level for the queries was ONE.