You seem to be asking two rather different questions:
- Is Java really slow, and if so why?
- Why is Java perceived as slow, even though it's faster than many alternatives?
The first of these is more or less a "how long is a rope" kind of question. It comes down to your definition of "slow". Compared to a pure interpreter, Java is extremely fast. Compared to other languages that are (normally) compiled to some sort of bytecode, then dynamically compiled to machine code (e.g. C# or anything else on .NET) Java is roughly on a par. Compared to the languages that are normally compiled to pure machine code, and have (often large) teams of people working on nothing but improving their optimizers (e.g. C, C++, Fortran, Ada) Java does pretty well at a few things, but overall tends to be at least somewhat slower.
A lot of this is related primarily to the implementation -- basically, it comes down to the fact that a user is waiting while a dynamic/JIT compiler runs, so unless you have a program that runs for quite a while to start with, it's hard to justify having the compiler spend a lot of time on difficult optimizations. Therefore, most Java (and C#, etc.) compilers don't put a lot of effort into really difficult optimizations. In a lot of cases, it's less about what optimizations are done, than where they're applied. Many optimization problems are NP complete, so the time they take grows quickly with the size of problem being attacked. One way to keep time within reason is to only apply the optimization to something like a single function at a time. When it's only the developer waiting for the compiler, you can afford to take a lot longer, and apply that same optimization to much larger chunks of the program. Likewise, the code for some optimizations is pretty hairy (and therefore can be pretty big). Again, since the user is waiting while that code loads (and the JVM startup time is often a significant factor in the overall time), the implementation has to balance time saved in one place vs. lost in another -- and given how little code benefits from the hairy optimizations, keeping the JVM small is usually more beneficial.
A second problem is that with Java, you frequently get a more or less "one size fits all" kind of solution. Just for example, for many Java developers Swing is essentially the only windowing library available. In something like C++, there are literally dozens of windowing libraries, application frameworks, etc., each with its own set of compromises between ease of use vs. fast execution, consistent look and feel vs. native look and feel, and so on. The only real sticking point is that some (e.g. Qt) can be quite expensive (at least for commercial use).
Third a lot of code written in C++ (and C even more so) is simply older and more mature. At lot of it contains a core of routines written decades ago, when spending extra time optimizing the code was normal, expected behavior. That often has a real benefit in code that's smaller and faster. C++ (or C) gets the credit for the code being small and fast, but it's really much more a product of the developer and the constraints of the time the code was written. To an extent, this leads to a self-fulfilling prophecy -- when people care about speed, they often select C++ because it has that reputation. They put extra time and effort into optimization, and a new generation of fast C++ code is written.
To summarize, the normal implementation of Java makes maximum optimization problematic at best. Worse, where Java is visible, such things as windowing toolkits and JVM startup time often play a larger role than the execution speed of the language itself anyway. In a lot of cases, C and C++ also get credit for what's really the product of simply working harder at optimization.
As to the second question, I think it's largely a matter of human nature at work. A few zealots make rather inflated claims about Java being blindingly fast. Somebody tries it out, and finds that even a trivial program takes a few seconds to get started, and feels slow and clumsy when it does run. Few probably bother analyzing things to realize that a great deal of this is the startup time of the JVM, and the fact that when they first try things out, none of the code has been compiled yet -- some of the code is being interpreted, and some being compiled while they wait. Worse, even when it runs fast enough, the look and feel will usually seem foreign and clumsy to most users, so even if objective measurements showed fast response times, it'd still seem clumsy.
Adding those together leads to a fairly simple and natural reaction: that Java is slow, ugly and clumsy. Given the hype saying it's really fast, there's a tendency to overreact and conclude think of it as horribly slow, instead of a (more accurate) "slightly slower, and that mostly under specific circumstances." This is generally at its worst for a developer writing the first few programs in the language. Execution of a "hello world" program in most languages appears instantaneous, but in Java there's an easily perceptible pause as the JVM starts up. Even a pure interpreter that runs much more slowly on tight loops and such will still often appear faster for code like this, simply because it can get loaded and started executing a bit sooner.