Now that I understand your data I would certainly use the original set in your analysis rather than the four averages. The "noise" that you describe is actually a crucial part of your data. The higher $R^2$ in the model with fewer data points is because you have taken out the variation around the means.
First, which of your two plots and regressions to use?
By using a technique like linear regression on your original data (the 120 points) you can simultaneously look at the average perceived velocity for each of your four levels of actual velocity, and conduct inference based on a full understanding of the level of variation in the data.
If you conduct it on just the four means, you have split your analysis into two phases. The first phase finds the average for each level of actual velocity; then the second (where you conduct regression) tries to do inference to the general population. You can't really do what you want to in this second phase because you have lost all the information about the randomness in your first phase.
You might want to come back to your picture of the four averages as part of a result-reporting summary of your data, but all inference should be based on a model fitted to the original set.
Second, what analysis to do
Because you have repeated observations with characteristics in common (eg different trials; and each observer with different goes) you can't just fit a regression to all 120 points. You need to somehow control for observer effects. I would fit a model like
perceived ~ actual * observer
while hoping that can be reduced to
perceived ~ actual + observer
For this to work properly
actual needs to be an ordered factor. R will then automatically apply the correct contrasts to it in fitting a model (sorry I don't have time to explain that better but there would be material on the web about what that means).
However, there are lots of potential fishhooks. Can perceived velocity really be treated as continuous? Does it have an approximately normal distribution (obviously not really, but it may be close enough)? Is the variance independent of the mean? Evading these will be tricky and you should use R's graphic capabilities fully in exploring your data. If the assumptions behind linear regression do not hold, you may be able to use the polr() function from library(MASS) to fit an ordinal response regression instead.