This is what worked for me, on an Intel-based HP Pavillon dv6000:

First of all, my puzzling started making sense only when I got rid of the Gnome CPU Frequency Scaling Monitor. It does and displays nonsense. For example, when the CPU is absolutely constantly at maximum speed, the Gnome applet will show that the CPU is mostly at minimum speed and sometimes rises at maximum speed.

I installed the sysfsutils package:

   sudo apt-get install sysfsutils

Which allowed to use this command line in a terminal window to monitor the frequency:

   while : ; do sudo cat /sys/devices/system/cpu/cpu0/cpufreq/cpuinfo_cur_freq ; sleep 1 ; done

Alternatively, for example if you don't want sysfsutils installed or you don't want to sudo, this command line should do the job:

   while : ; do cat /proc/cpuinfo | grep MHz ; sleep 1 ; done

Then, I had to install powernowd:

   sudo apt-get install powernowd

The presence of the powernowd package is what makes everything perform properly. Actually the powernowd daemon does not run on my system... It seems that it will not be started if the default governor is "ondemand". But anyway the package needs to be installed.

I had some doubts about the gnome-power-manager package but simply it seems to have no influence on this problem. I keep it so I can suspend the machine without having to type "sudo pm-suspend" in a terminal window. Some online texts made me believe that gnome-power-manager has an influence on the CPU frequency but gconf-editor doesn't show that there would be any related tuning. (The gnome-power-manager has a mostly nonsensical behavior, for example using its graphical interface often yields no or opposite results and the default behavior is very annoying. I used gconf-editor to just shut down most of its features.)

With the powernowd package installed, my machine suddenly became fast as craziness. The maximum speed is switched on instantaneously when required. It's a delight. No more need to purchase a new laptop. I lack an applet to monitor the frequency but actually this is not severe. I simply know that when at least on of the cores is fully busy, the CPU will be at maximum frequency. Also, I do no more need the applet to be able to tune maximum frequency when needed, because powernowd does it perfectly and automatically. 

The only case when I need to tune the frequency is to impose a constant low frequency to avoid the machine heating or making noise in some occasions. I found no clean procedure to do that. Powernowd is unaware of the need to sometimes keep the machine at low power consumption. The commands below allow to do that but they have no effect on my system, whether or not powernowd is installed.

   sudo su
   echo ondemand > /sys/devices/system/cpu/cpu0/cpufreq/scaling_governor
   exit

or:

cpufreq-selector -g ondemand

Linux is a strange system. It has a whole set of different tools for one purpose. Each tool is incomplete, has bugs and quite often the configuration procedure is obfuscated beyond repair. A computer scientist can often manage to assemble the working parts of some tools to get something that works for an individual case. But no distro maintainers ever managed to assemble something that would be general-purpose and reliable. A few years ago I managed to tweak the kernel to almost get a really multitasking multimedia system, with almost no stuttering in operation. But the kernel changed and the work was to begin again from zero so I abandoned. I also needed several months till I found on the internet that to stop the X server from bleeding away all the memory in a few hours time, you just need to disable Xinerama in /etc/X11/xorg.conf. Some of those problems really need work to fix, yet other ones are just a quick tuning that can be installed automatically with the next package upgrade. But, even if plainly reported and documented inside the distro's mailing lists since years, the fix will never be implemented... When you complain, at best you get no reply, at worst you get a flaming response from a developer (or from one of his followers if he's already too deified to address common people) explaining how repugnant you are for not seeing the brilliance of his courageous choices. The best one I ever got is after simply reporting in a forum that ext2 was the sole format that always allowed me to recover my files after a severe crash and that ext3 was the only one that even never crashed at all. I got a flaming reply stating that a file system format *must not* be in charge of the integrity of the data and that each individual software has to do the necessary work to restore its files...

I believe that the human brain is capable to make a decent operating system but mankind is not. The only way out of this is to impose a new abstraction layer; that of hardware virtualization. It is already often used but in a partial way or as a simplification at the behalf of performance. It must become completely detached from the operating system business and be a sector of its own, just like the operating system business became detached from the application business.