How do I resolve this paradox of counting line segments?
Your argument does prove something. Namely, it proves:
There is no uncountable set of reals which is right-discrete - every element in the set has a next element in the set.
(Note that you talk about transcendentals specifically, but there is nothing special about them - we can just talk about reals. And the same statement is true for left-discrete sets, of course.)
The proof is exactly the argument they give. Suppose $X$ were a discrete uncountable set of reals. Then to each $x\in X$ we can assign an interval $I_x$ to $x$: let $I_x=(x, y)$ where $y$ is the next element of $X$.
Now this construction begs the question: $$\mbox{How do we know there is such a $y$ in the first place?}$$ Well, we know that because $X$ is discrete (by assumption). So we're good to go. But note that this step is not true for general $X$.
OK, now we argue as follows. Let $q_x$ be some rational in $I_x$; there are lots of rationals in $I_x$ since $x<y$, so this is doable (and the rationals are well-orderable (not well-ordered - careful!), so we may always "pick one" even without the axiom of choice). But it's easy to show that $I_u\cap I_v=\emptyset$ if $u, v$ are distinct elements of $X$, so the map $x\mapsto q_x$ is an injection from $X$ into $\mathbb{Q}$; and this contradicts the assumption that $X$ was uncountable. $\quad \Box$
(Aw heck, I committed the "logician's sin" - I wrote a proof by contradiction where none is needed! We can just argue directly that if $X$ is right-discrete, then $X$ is countable, by building the injection into $\mathbb{Q}$. I wrote this as a proof by contradiction instead, to better parallel the OP's argument.)
But this is not what you claimed! The result you want is (somehow) that there is no uncountable set of transcendentals; and neither that nor any related statement is true. The only way your argument works at all is if the set in question is assumed to be discrete, or "pretty discrete" anyways.
Let's suppose for a moment that we know that between any two transcendentals there's another transcendental. The let your set $S$ contain all transcendentals, and let's follow your argument.
Now suppose I take the complement of this set. I now have a set of line segments defined in-between each pair of points, one fewer segments than there were transcendental numbers the original set
So we take all non-transcendental numbers, and you say that this consists of a set of line segments, one between each pair of points. (I assume you mean here "between each adjacent pair of points", i.e., that your segments do not overlap). Suppose $(p, q)$ is such a segment, i.e., that $p$ and $q$ are adjacent transcendentals. Then there's a transcendental between $p$ and $q$, by our assumption at the top of this answer. So they're not actually "adjacent". In short, with the assumption at the top (and the assumption of nonoverlapping intervals), your construction fails.
On the other hand, if the intervals are allowed to overlap, then for each transcendental $p$, you just take the interval $(p, p+1)$. There's certainly one rational in this interval, and indeed, infinitely many. And all rationals get counted infinitely many times, so you cannot say that the number of intervals is countable.
Once more, let's follow your construction. It's supposed to work for any set of uncountably many transcendental numbers, so I'm going to take as my set $S$ the set of all transcendentals.
Useful lemma: because $\pi$ is transcendental, $q_n = (1 + \frac{1}{n})\pi$ is also transcendental.
Proof: suppose that for some polynomial $p$, $p(q_n) = 0$. Let $$ s(x) = p(\left(\frac{n}{n+1}\right) x). $$ Then $s(\pi) = 0$, and that's a contradiction. QED.
(1) I take the complement of this set, and you say that I have the set of (open) line segments defined in between points.
(2) Because $\pi \in S$, you claim there must be a line segment starting at $\pi$ and going to the next transcendental, which I'll call $t$.
(3) Because $t$ is the next transcendental, there are no transcendentals between $\pi$ and $t$. [Stop me when I say something that's not what you intended!]
(4) Let's look at the number $t - \pi$.
(5) Because $q_1 = 2\pi$ is transcendental, by the lemma, we must have $t < q_1$, so $t - \pi < \pi$.
(6) Because $q_2 = \frac{3}{2} \pi$ is transcendental, by the lemma, we must have $t < q_2$, so $t - \pi < \frac{\pi}{2}$.
(7) By the same argument, for any integer $n$, we have that $t - \pi < \frac{\pi}{n}$.
(8) Hence $t \le \pi$. But since $t$ is the "next" transcendental, we know that $t > \pi$.
That's a contradiction.
Your assumption that there's a "next" irrational, made in step 2, must be false.