Strictly, it's never necessary to measure in different bases, because any projective measurement can be decomposed as a unitary followed by a projective measurement in the computational basis. Conversely, there are times when algorithms are described as unitaries followed by measurements in the computational basis, and you might choose to move some of those unitaries into a description of the basis.
The point I'm trying to make here is that the division between measurement and the rest of an algorithm is fairly arbitrary, so to get to the heart of your question, we really have to ask about the importance of relative phases inside a quantum algorithm. These are absolutely crucial, as these are what provide for the constructive and destructive interference that permit outcomes different from classical computation. Take a look at Deutsch's algorithm for the simplest, 1 qubit, example. This is usually described as -prepare $|0\rangle$ state, Hadamard, function evaluation, Hadamard, measure in computational basis- but you could describe it as -prepare $|+\rangle$ state, function evaluation,measure in $|\pm\rangle$ basis-. The function evaluation, the thing you really want to get at, is entirely encoded in the relative phase between the two states.
To give one extreme example, consider measurement-based quantum computation. Here, we produce a standard quantum state, and the computation to be performed is entirely defined by the choice of single-qubit measurements that are performed.
