What is it that quantumness provides that sieve techniques cannot provide?
It is more a question why quantum computers are believed to be more powerful than classical computation models. Short: Quantum computers provide superpositions of quantum states.
Randomized algorithms are restricted to be in a certain state with some (constant) error probablility. Quantumness provides the posibility of evaluating function on every possible state and afterwards measuring a certain state with some error probability.
What exact barrier does Shor's algorithm break that randomness cannot?
The quantum states represent the accepted states as well as the rejected states. Shor's algorithm evaluates the accepting states in such an extent that the accepting states are more likely to be measured. Also the quantum algorithm can manipulate all states at the same time. A randomized algorithm is bound to increase the probability of being in such a accepting state, looping often enough to get a certain probability (or extending some other variable).