Relativity of temperature paradox
Temperature is related to kinetic energy in the rest frame of the fluid/gas. In non-relatvistic kinetic theory the distribution function is $$ f(p) \sim \exp\left(-\frac{(\vec{p}-m\vec{u})^2}{2mT}\right) $$ where $\vec{u}$ is the local fluid velocity. The velocity can be found by demanding that the mean momentum in the local rest frame is zero. Then $\vec{u}$ transform as a vector under Galilean transformations, and $T$ is a scalar.
In relativistic kinetic theory $$ f(p) \sim \exp\left(-\frac{p\cdot u}{T}\right) $$ where $p$ is the four-momentum, $u$ is the four-velocity, and $T$ is the temperature scalar. The rest frame is defined by $\vec{u}=0$, and in the rest frame $f\sim \exp(-E_p/T)$, as expected.
The relativistic result is known as the Juttner distribution (Juttner, 1911), and is discussed in standard texts on relativistic kinetic theory, for example Cercignani and Kremer , equ. (2.124), and de Groot et al , equ (ch4)(25). See also (2.120) in Rezzolla and Zanotti. For an intro available online see equ. (55-58) of Romatschke's review. Neumaier notes that some (like Beccatini ) advocate defining a four-vector field $\beta_\mu=u_\mu/T$, and then define a frame dependent temperature $T'\equiv 1/\beta_0$. I fail to see the advantage of this procedure, and it is not what is done in relativistic kinetic theory, hydrodynamics, numerical GR, or AdS/CFT.
Ultimately, the most general definition of $T$ comes from local thermodynamics (fluid dynamics), not kinetic theory, because strongly correlated fluids (classical or quantum) are not described in kinetic theory. The standard form of relativistic fluid dynamics (developed by Landau, and explained in his book on fluid dynamics) also introduces a relarivistic 4-velocity $u_\mu$ (with $u^2=1$), and a scalar temperature $T$, defined by thermodynamic identities, $dP=sdT+nd\mu$. The ideal fluid stress tensor is $$ T_{\mu\nu}=({\cal E}+P) u_\mu u_\nu -Pg_{\mu\nu} $$ where ${\cal E}$ is the energy density and $P$ is the pressure. Note that for a kinetic system the parameter $u_\mu$ in the Juttner distribution is the fluid velocity, as one would expect. More generally, the fluid velocity can be defined by $u^\mu T_{\mu\nu}={\cal E}u_\nu$, which is valid even if dissipative corrections are taken into account.
Regarding the ``paradox'': Temperature is not relative, it is a scalar. The relation in B is only correct in the rest frame. The Doppler effect is of course a real physical effect. The spectrum seen by an observer moving vith relative velocity $v$ is $f\sim\exp(-p\cdot v/T)$, which exhibits a red/blue shift. The spectrum only depends on the relative velocity, as it should. Measuring the spectrum can be used to determine both the relative velocity and the temperature. However, if you look at a distant star you only measure light coming off in one direction. Then, in order to disentangle $u$ and $T$, you need either a spectral line, or information on the absolute luminosity.
[June 19,2016: thoroughly revised, giving a more detailed, comparative presentation and better references]
General case. In relativistic thermodynamics, inverse temperature $\beta^\mu$ is a vector field, namely the multipliers of the 4-momentum density in the exponent of the density operator specifying the system in terms of statistical mechanics, using the maximum entropy method, where $\beta^\mu p_\mu$ (in units where $c=1$) replaces the term $\beta H$ of the nonrelativistic canonical ensemble. This is done in
C.G. van Weert, Maximum entropy principle and relativistic hydrodynamics, Annals of Physics 140 (1982), 133-162.
for classical statistical mechanics and for quantum statistical mechanics in
T. Hayata et al., Relativistic hydrodynamics from quantum field theory on the basis of the generalized Gibbs ensemble method, Phys. Rev. D 92 (2015), 065008. https://arxiv.org/abs/1503.04535
For an extension to general relativity with spin see also
F. Becattini, Covariant statistical mechanics and the stress-energy tensor, Phys. Rev. Lett 108 (2012), 244502. https://arxiv.org/abs/1511.05439
Conservative case. One can define a scalar temperature $T:=1/k_B\sqrt{\beta^\mu\beta_\mu}$ and a velocity field $u^\mu:=k_BT\beta^\mu$ for the fluid; then $\beta^\mu=u^\mu/k_BT$, and the distribution function for an ideal fluid takes the form of a Jüttner distribution $e^{-u\cdot p/k_BT}$.
For an ideal fluid (i.e., assuming no dissipation, so that all conservation laws hold exacly), one obtains the format commonly used in relativistic hydrodynamics (see Chapter 22 in the book Misner, Thorne, Wheeler, Gravitation). It amounts to treating the thermodynamics nonrelativistically in the rest frame of the fluid.
Note that the definition of temperature consistent with the canonical ensemble needs a distribution of the form $e^{-\beta H - terms~ linear~ in~ p}$, conforming with the identification of the noncovariant $\beta^0$ as the inverse canonical temperature. Essentially, this is due to the frame dependence of the volume that enters the thermodynamics. This is in agreement with the noncovariant definition of temperature used by Planck and Einstein and was the generally agreed upon convention until at least 1968; cf. the discussion in
R. Balescu, Relativistic statistical thermodynamics, Physica 40 (1968), 309-338.
In contrast, the covariant Jüttner distribution has the form $e^{-u_0 H/k_BT - terms~ linear~ in~ p}$. Therefore the covariant scalar temperature differs from the canonical one by a velocity-dependent factor $u_0$. This explains the different transformation law. The covariant scalar temperature is simply the canonical temperature in the rest frame, turned covariant by redefinition.
Quantum general relativity. In quantum general relativity, accelerated observers interpret temperature differently. This is demonstrated for the vacuum state in Minkowski space by the Unruh effect, which is part of the thermodynamics of black holes. This seems inconsistent with the assumption of a covariant temperature.
Dissipative case. The situation is more complicated in the more realistic dissipative case. Once one allows for dissipation, amounting to going from Euler to Navier-Stokes in the nonrelativistic case, trying to generalize this simple formulation runs into problems. Thus it cannot be completely correct. In a gradient expansion at low order, the velocity field defined above from $\beta^\mu$ can be identified in the Landau-Lifschitz frame with the velocity field proportional to the energy current; see (86) in Hayata et al.. However, in general, this identification involves an approximation as there is no reason for these velocity fields to be exactly parallel; see, e.g.,
P. Van and T.S. Biró, First order and stable relativistic dissipative hydrodynamics, Physics Letters B 709 (2012), 106-110. https://arxiv.org/abs/1109.0985
There are various ways to patch the situation, starting from a kinetic description (valid for dilute gases only): The first reasonable formulation by Israel and Stewart based on a first order gradient expansion turned out to exhibit acausal behavior and not to be thermodynamically consistent. Extensions to second order (by Romatschke, e.g., https://arxiv.org/abs/0902.3663) or third order (by El et al., https://arxiv.org/abs/0907.4500) remedy the problems at low density, but shift the difficulties only to higher order terms (see Section 3.2 of Kovtun, https://arxiv.org/abs/1205.5040).
A causal and thermodynamically consistent formulation involving additional fields was given by Mueller and Ruggeri in their book Extended Thermodynamics 1993 and its 2nd edition, called Rational extended Thermodynamics 1998.
Paradoxes. Concerning the paradoxes mentioned in the original post:
Note that the formula $\langle E\rangle = \frac32 k_B T$ is valid only under very special circumstances (nonrelativistic ideal monatomic gas in its rest frame), and does not generalize. In general there is no simple relationship between temperature and velocity.
One can say that your paradox arises because in the three scenarios, three different concepts of temperature are used. What temperature is and how it transforms is a matter of convention, and the dominant convention changed some time after 1968; after Balescu's paper mentioned above, which shows that until 1963 it was universally defined as being frame-dependent. Today both conventions are alive, the frame-independent one being dominant.
In the kinetic theory of gases, you only really define the temperature for molecules that are in constant, random, and rapid motion. So if you have a container with a gas at temperature $T$ you don't change the internal energy of the gas by uniformly moving the container. Uniformly moving the container gives all the molecules a non-zero average motion, but it doesn't affect the random motion of the molecules that make up the gas.