Kirk was out on the frontier exploring new places
ten years after this series is set, and he was still running into Klingons all the time - two or three times a season after the first year.
The obvious reason for that is that the Federation and the Klingons shared a frontier - they both had well-explored areas of space that they controlled and were both pushing aggressively into the same unexplored areas.
There's no contradiction between new worlds and bumping into the occasional Klingon.
Remember that the model for
Star Trek was not really primarily speculative fiction, nor scientific extrapolation, but the tropes of space opera - and that was based upon the European exploration and exploitation of the rest of the world in the 17th, 18th and 19th centuries. French and Spanish and Portuguese and English and eventually Americans explored and competed with each other for territory and resources and alliances all over the globe.
You've gotta wonder, though - the Klingons had to be bumping into different kinds of aliens than Kirk used to run into. A lot of those superpowered critters would have kicked Klingon ass if the bumpheads had come on all macho. Kirk had the virtue of a sometimes, uh, flexible approach to problem solving.
You wanna be "tired of Klingons," go be tired of 'em in the 32nd century.
