The answer is that the wave changes shape depending upon how it interacts with things. Sometimes the wave is very spread out and sometimes it is very localised. When it is spread out you can't say exactly where it is, obviously, and when it is vey localised it doesn't have a well-defined wavelength, and since the particle's velocity is determined by the wavelength of the associated wave, that means it doesn't have a well defined velocity when the wave is localised.
So, in a nutshell, when the wave is very localised it has a well-defined position but no definite wavelength (which equates to the velocity) and when the wave has a very well-defined wavelength (velocity) it doesn't have a well-defined position.
Incidentally, you shouldn't really think of the wave as being the particle. The wave is a mathematical function that encodes information about the position and momentum of the particle. The momentum is related to the wavelength of the function, and the position is given just as a probability as a function of the amplitude of the wave at any point in space.
Clearly you can record a particle's position and then measure its velocity, but the point is that when you measure its velocity it is no longer is in the position it was in when you recorded it. Likewise you can measure and record its velocity and then perform an experiment which nails down its position, but by performing the experiment you change the shape of the wave which means the particle no longer has the velocity you recorded.
What is especially lovely about quantum mechanics when you get into it is the way that the probabilities of getting specific experimental results arise from interrelationships between things known as eigenfunctions of operators. The idea is too complicated to explain slowly here, but it is very sweet when you get to understand it.