You have pinpointed an important nuance of quantum information theory.
A perfectly entangled state is, in some sense, like a single bit in a one time pad: just two copies of a shared random bit. In fact, the teleportation protocol is perfectly analogous — not the same, but certainly analogous — to transmitting a message securely using a one-time pad: Alice performs a Bell-basis measurement (which corresponds to taking the parity of a data bit and a bit of the one-time pad); she communicates the result of the measurement to Bob (corresponding to transmitting the outcome of the parity computation); and Bob performs a Pauli transformation on his qubit (corresponding to a single-bit operation depending on the parity bit that he recieves). The correspondance between the protocols of teleportation and encoding with one-time pads is perfect.
The reason why teleportation is not the same as encoding with a one time pad is the same why entanglement is not the same as shared randomness: a perfectly entangled state cannot be described by random bits which describe the as-yet unmeasured outcome of any measurement. That is to say, there is no local hidden variable model for the entangled state — it is in this sense totally unlike a shared random bit. Indeed, no number of shared random bits can represent the entangled state.
Note that this lack of hidden variable models (at least, models in which some random variable is simply revealed by measurement) is not just restricted to entangled state. By the Kochen-Specker theorem, this holds even for single-spin states, at least for spin-1 particles. Furthermore, the difference between an entangled state and a merely shared random bit is expressible precisely by the correlations in the multiple degrees of freedom for measuring a single spin. So the mystery behind entanglement and teleportation is basically the same mystery as there is behind the existence of more than one incompatible basis of measurement for a single spin. It is in some sense a happy coincidence that protocols such as sending secret messages securely, as if by a one-time pad, carry through for quantum states.