Graphene does have a two-atom basis. The point is made graphically very clearly in the Wikipedia page you quote, which includes this figure:
The honeycomb lattice includes two different site types, which are labelled in red and green in the image. In graphene, both of these sites are populated with identical carbon atoms, but that is irrelevant to the periodicity of the lattice structure. In essence, there simply is no way to create a proper unit cell (where "proper" here is equivalent to "shaped as a parallelogram") which only includes one green atom and no red atoms (or vice versa) and which tiles the plane as a Bravais lattice.
You can, of course, cut up the unit cell of the Bravais lattice into two equivalent triangular sectors, and tile the plane with those. But the resulting tiling is not a Bravais lattice, which requires every copy of the unit cell to be obtained from the primal unit cell by a displacement of the form $\mathbf d_{n_1,n_2} = n_1 \mathbf a_1 + n_2 \mathbf a_2$ (and, therefore, without any rotations or reflections or additional symmetry operations).
That said, of course, when you say
I'd think it's more accurate to refer to it as a hexagonal lattice.
all honeycomb lattices are also hexagonal lattices, as you should already be aware of (since it is in the quote in your question). But graphene is in the special case, not in the general hexagonal-lattice category.