I recently read Steve Seow's book, Designing and Engineering Time: The Psychology of Time Perception in Software. Steve is an expert on performance engineering at Microsoft, and really understands the human element and psychology behind software performance.
A really interesting take-away is that users do not notice changes in performance below a certain threshold. Research has shown that for durations under 30 seconds, users do not detect differences up to 18%. Steve's rule of thumb is that users really won't notice performance changes of +/- 20%. So if you are looking at setting goals for a performance improvement, or considering performance against a competitive product, your goals should be to gain at least 20% over the baseline measurement.
Likewise if you are considering whether or not to fix a performance regression, 20% is a good measurement to consider. If the regression is less than 20%, users likely won't detect the degradation, so you may be better off spending your effort elsewhere.
Of course this is a slippery slope. If each release you allow a 20% degradation, users certainly will notice and stop using your software. So it is important to maintain and meet performance goals that will keep your users happy with your software. One of my performance testing customers ends his emails with this quote:
"If it is fast and ugly, they will use it and curse you; if it is slow, they will not use it."
-David Cheriton in _The Art of Computer Systems Performance Analysis_