Initially Java was not particularly fast, but it is not overly slow either. These days, Java is very fast. From the people I've talked to the impression of Java being slow comes from two things:
Slow VM startup time. The early Java implementation took a long time to start up and load the require libraries and the application compared to native applications.
Slow UI. Early Swing was slow. It probably did not help that most Windows users found the default Metal L&F ugly either.
Given the above points, it's no wonder people got the 'Java is slow' impression.
For users or developers used to developing native applications, or even Visual Basic applications, these two points are the most visible thing in an application, and it is the first impression you will get about an application (unless it's a non-GUI application in which case only the 1. applies.).
You will not convince a user that "it executes code very fast" when the application takes 8 seconds to start vs. his old Visual Basic application that starts immediately - even though code execution and startup time might not be connected at all.
Ruining the first impression is a great way to start rumors and myths. And rumors and myths are hard to kill.
In short, Java is not slow. People having the "Java is slow attitude" is based on first impressions of Java more than 10 years ago.