Besides the speed of sound, what else changes when the transmitting medium changes? Say from Oxygen to Hydrogen. I'm pretty sure the loudness does not change, but I think you would HEAR a change in pitch, because I think the wavelength changes when the transmitting medium changes. I don't think speed changes anything you hear. The main question is.... Can you hear a difference if you change the transmitting medium?
The short answer is yes. Sound waves are greatly affected by the medium in which they travel, not just in terms of speed, but also in terms of loudness and tonal quality. Just think of the variation in loudness and sound quality of different acoustic guitars which may use the same strings, but the sound is greatly affected by the different media in which it travels, including the wood, sound cavities, even the varnish on the instrument.
By considering 'sound' as the result of the propagation of pressure waves through a mechanical medium such as any solid, liquid or gas, the 'speed of sound' can be shown to be a function of the elastic and inertial properties of the medium, such that:
For example, the speed of sound through a gas with Bulk Modulus (elastic property) $B$ and volume density (inertial property) $\rho$, is given by:
The speed of sound also depends on the temperature of the medium.
Now, the 'loudness' and 'pitch' of a sound are psychological phenomena which generally correlate to the physical phenomena of intensity and frequency, however there are some subtle differences, some of which relate to physiology of the ear drum.
The wavelength of sound changes with the medium, because it is proportional to the wave speed.
The frequency however is generally independent of the medium, although it can vary with the relative velocity of the sound source with respect to the observer, due to the Doppler Effect.
The 'pitch' heard relates to the perception of frequency of a sound vibration. It is dependent upon the physiology of the ear drum such as age. The relation between (perceived) pitch and frequency is not linear.
Also, the ear perceives sound not just in terms of loudness and pitch, but also tone quality (timbre) which is affected by the medium.
The intensity of a sound wave (power per unit area) is the rate at which the energy transported by the wave transfers through a unit area $A$ and is generally proportional to the volume density of the medium, so the more dense the medium, the more power per unit area (wave intensity).
The 'loudness' of a sound is not only a function of wave intensity, but of physiological conditions within the ear drum which affect the frequency response of loudness perception. This is typically characterised in the 'Equal Loudness Curve'.
The perception of sound qualities other than loudness and pitch are often referred to as 'timbre'. This encompasses effects of the sound 'envelope' (attach-decay-sustain-release) as well as spectral differences (relative weighting of harmonic content, combination tones and resonant characteristics) as well as temporal relationships such as reverberation. Timbre is heavily affected by different sound medium,
In summary, you can hear a difference if you change the sound transmission medium. Firstly in terms of loudness (eg: an acoustic guitar will) and secondly in terms of perceived pitch (which is affected by loudness) as well as timbre (tone quality) which, although somewhat subtle and difficult to detect through scientific measurement, is nonetheless perceptible and measurable by the human ear and through advanced digital signal processing techniques.
As you correctly pointed out, the wavelength of a sound wave would change as it experiences a change in medium. However, this does not mean that the pitch, which is related to the frequency, would change. In fact, it shouldn't change. In general, there will reflections of the wave upon a change of medium. Therefore, the 'loudness' which is related to the amplitude of the wave, will also change.
To answer your main question, you can hear a difference if you change the transmitting medium. An extreme example is if you are in space (or any place close to resembling a vacuum). There wouldn't even be particles to transmit your sound waves, so you wouldn't hear a thing.
Here's a weird effect: the direction that you think the sound is coming from can change. You might think that the sound is coming from somewhere other than its actual source.
This is due to the bending of wavefronts when you go from one medium to another, the same effect that makes it look like a pencil bends when you put it into a glass of water. Here's a link to a great diagram of this at Wikimedia Commons, using a ray model, and another diagram from Davidson AP Physics that uses the a wave model.