You are assuming that order doesn't matter in the second case, but this is the wrong assumption. Order definitely matters. You have, in the case of $n=6$ a sample space of $6^2$ Even though when you finally pull both tags out, a $(2,1)$ is the same as $(1,2)$, these are still different events and must be treated differently. Since this is the case, let's look at $n=6$. All consecutive numbers then would be;
$$(1,2),(2,1),(2,3),(3,2),(3,4),(4,3),(4,5),(5,4),(5,6),(6,5)$$
So here you have 10 events that are possible, not 5. And your sample space is 36... Therefore, your probability is
$$\frac{10}{36}=\frac{2\cdot5}{6^2}=\frac{2(6-1)}{6^2}$$
And this makes sense. You can only have $n-1$ consecutive pairs, since the $n$-th pair would be $(n,1)$ which are not consecutive, and our sample space consists of $n^2$ events. Since there are two ways to get consecutive integers, the formula is
$$P(\text{consecutive numbers with replacement of n tags})=\frac{2(n-1)}{n^2}$$
Also, in the first case, again, you are making the faulty assumption that $(1,2)$ is the same as $(2,1)$ and I think that you make this assumption because the probability is correct under both assumptions, i.e., yours, and the correct assumption. Why?
The sample space under sampling without replacement is in the case of $n=6$ is $6\cdot5=30$. This is the case because pairs such as $(1,1), (2,2)$ are impossible without replacement. However, you can still get the ten pairs of consecutive numbers listed above, so therefore, under the correct assumption
$$P(\text{consecutive numbers without replacement of n tags})=\frac{2(n-1)}{n(n-1)}=\frac2{n}$$
If $n=6$, you get your probability is $\frac1{3}$, which is what you got under your faulty assumption. Hope this helps shed a little light.
Edit: Usually, these sorts of probabilities are always defined in terms of natural density. So when I say below that "the probability that $x$ is divisible by $p$ is $1/p$", this means that, if we pick a random $x$ in $\{1,\dots,N\}$, and ask about the probability that $x$ is divisible by $p$, and then let $N\to\infty$, we arrive at the intuitive fact that the probability is $1/p$.
Multiples of $p$ occur every $p$ integers, so the probability that $p$ divides $x$ is $1/p$.
For distinct primes, the events are independent, so you have probability $$\frac1{p_1}\cdot\frac1{p_2}=\frac1{p_1p_2}.$$
Best Answer
The words "with replacement" means that after you pull out the first tag and read the number on it, you put it back ("replace it"), mix the tags up again before you pull out the second one.
Back to the question. Your idea of breaking into cases is a sound one, and the probability is indeed $P_1 + P_2$, but your expressions for those two numbers are not correct.
Case I: The probability that the first one you draw is neither $1$ or $n$ is $\frac{n-2}{n} $. This is then multiplied by the probability that the second number you draw is one of the two adjacent numbers, which is $\frac{2}{n}$ (note that it's not $\frac{2}{n-1}$, since we put the first tag back). We therefore have $$ P_1 = \frac{n-2}{n}\cdot \frac{2}{n} $$
Case II: The probability that the first tag is either $1$ or $0$ is $\frac{2}{n}$. The probability that the second tag in that case is the one adjacent tag number (either $2$ or $n-1$, depending on the case) is $\frac{1}{n}$. So we have $$ P_2 = \frac{2}{n}\cdot \frac{1}{n} $$
So we get $$ P_1 + P_2 = \frac{2n-4 + 2}{n^2} = \frac{2n - 2}{n^2} $$
Alternate approach: (assumes $n \geq 3$, if $n = 2$ the probability is easily seen to be $0.5$) Pretend, for a second, that we also allowed $1$ and $n$ to "connect around", so that drawing those two in any order would also count. Then no matter what you got on the first tag, there would be $2$ possible "good" second tags. So the probability would be $\frac{2}{n}$.
Now, how much probability do we lose by disallowing the $1$-$n$-connection? Well, there are $n^2$ different combinations to draw, and there are two of those possibilities that are $1$ and $n$, in some order. Therefore, the probability that you draw a $1$ and an $n$ is $\frac{2}{n^2}$. That combination is allowed in our hypothetical scenario above, but it is disallowed in the real problem, so our $\frac{2}{n}$ result overshot the target by $\frac{2}{n^2}$. Therefore the probability of drawing two adjacent tags is $$ \frac{2}{n} - \frac{2}{n^2} = \frac{2n -2}{n^2} $$ which is the same result.