This question may sound a bit dumb. Why can't we obtain the Hamiltonian of a system simply by finding $\dot{q}$ in terms of $p$ and then evaluating the Lagrangian with $\dot{q} = \dot{q}(p)$? Wouldn't we obtain then a Lagrangian expressed in terms of $t$, $q$ and $p$?
Why do we need to use
$$H(t, q, p) = p\dot{q} - L(t, q, \dot{q})?$$
Or is it that whatever the Lagrangian is the method of finding $\dot{q}=\dot{q}(t,q,p)$. Will give us that equation for $H$?
A fairly basic remark to make is that usually we can plainly identify
$$L = T-U$$
where $T$ is the kinetic energy and $U$ is the potential energy, and
$$H = T+U$$
Expressing these quantities for e.g. a Hooke-like spring (or any system where $U\neq 0$) would give you a problem with the sign of $U$ if you simply substitute the expression you find for $\dot{q}(p)$ into the Lagrangian.$^1$ So the Hamiltonian is definitely not just the Lagrangian with $\dot{q}$ expressed in terms of $p$.
More mathematically expressed, the Hamiltonian is defined as the Legendre transform of the Lagrangian. (for some elaboration on the Legendre transformation - particularly in the context of the Lagrangian and Hamiltonian - see my answer here, as well as the other answers to that question)
$^1$ Indeed, the Lagrangian for such a (1D) system would be
$$L(q,\dot{q}[,t]) = \frac{m\dot{q}^2}{2} - \frac{kq^2}{2}$$
for which the canonically conjugate momentum is
$$p = \frac{\partial L}{\partial \dot{q}} = m\dot{q}$$
and therefore
$$\begin{align} H(q,p[,t]) &= m\dot{q}\cdot\dot{q} - \frac{m\dot{q}^2}{2} + \frac{kq^2}{2} \\ &= \frac{m\dot{q}^2}{2} + \frac{kq^2}{2} \\ H(q,p[,t]) &= \frac{p^2}{2m} + \frac{kq^2}{2}. \end{align}$$
Just inserting $p$ into the Lagrangian would yield
$$\frac{p^2}{2m} - \frac{kq^2}{2}.$$
Note the sign difference of the second term.
While I appreciate that Wouter's response shows that you can not indeed just perform the aforementioned substitution, it really doesn't answer the question (i.e. why doesn't the substitution work) in my opinion.
The underlying confusion probably comes from the fact that in mathematics if substitution $\dot{q}(p)$ is inserted in $f\left(t,q,\dot{q}\right)$ you will certainly end up with a function $f\left(t,q,\dot{q}\right)=g\left(t,q,p\right)$.
The real answer to the question then, is that Lagrangian and Hamiltonian formalisms are just two different paradigms, and no matter what you put in the Lagrangian instead of $\dot{q}$ you will always end up with another Lagrangian (but for a different problem). In other words the $L$ in front of $\left(t,q,\dot{q}\right)$ has different implications than the $H$, such as stationary action, $n$ second order equations for $n$ coordinates (where $n$ is the number of the degree of freedoms) vs. $2n$ first order equations for $2n$ coordinates, etc. This is unlike the case in mathematics where $f$ carries no other assumption different to $g$.
What you wrote is a variable change in the frame of the same Lagrangian. It remains a Lagrangian.
I would argue that the reason your method fails is because the conversion between Lagrangian and Hamiltonian dynamics is not a simple substitution, but through the mathematical transformation of coordinate bases known as a Legendre transformation, given in terms of the Hamiltonian and Lagrangian functions $$H\left(q,p\right) = \frac{\partial L}{\partial \dot{q}}\dot{q}-L\left(q,\dot{q}\right)$$
As Wouter points out, the transformation you offer does not actually give the correct transformation.
Calculating a Hamiltonian from a Lagrangian leads us to a new quantity, which is a function of coordinates and momenta. If you simply substitute velocity as a function of momentum into the Lagrangian, then the "Hamiltonian" will depend on velocity implicitly. This is not what we want.
Let me show you an example to explain why Hamiltonian (the usual one) does not depend on velocity. Let's say the system is 1-dimensional. So the Lagrangian is $L=L(q,\dot q)$. The Euler-Lagrangian equation is
$\frac{\mathrm{d}}{\mathrm dt}\frac{\partial L}{\partial \dot q}=\frac{\partial L}{\partial q}$.
The canonical momentum is $p=\partial L/\partial \dot q$. If we do Legendre transformation, we have
$H(p,q)=p\dot q-L(q,\dot q(p))$
and consider the variation of $H$:
$\delta H=p\delta \dot q+\dot q\delta p-\frac{\partial L}{\partial q}\delta q-\frac{\partial L}{\partial\dot q}\delta \dot q$.
We can now plug in the definition of $p$:
$\delta H=\dot q\delta p-\frac{\partial L}{\partial q}\delta q$
which shows that $H$ is not an explicit function of $\dot q$, which is what we want.
