I see the same symptoms on AMD Mobile Athlon 64 3700+, ASUS Z80K 2.6.17-10-generic kernel, out-of-the-box installation of ubuntu 6.10. 
BIOS version 0208.003.
PowerNow! is enabled in the BIOS, frequency scaling worked uder Windows XP with CPU RightMark.

More info:

k@tt-z80k:~$ sudo dmesg | grep -i power
Password:
[   18.500242] ACPI: Power Resource [GFAN] (off)
[   49.534598] ACPI: Power Button (FF) [PWRF]
[   49.534633] ACPI: Power Button (CM) [PWRB]
[   49.873456] powernow-k8: Found 1 AMD Athlon 64 / Opteron processors (version 1.60.2)
[   49.880367] powernow-k8: BIOS error - no PSB or ACPI _PSS objects
k@tt-z80k:~$ sudo /etc/init.d/powernowd restart
 * Stopping powernowd:                                                   [ ok ] 
 * Starting powernowd...                                                        /etc/init.d/powernowd: 156: cannot create /sys/devices/system/cpu/cpu0/cpufreq/scaling_governor: Directory nonexistent
 * CPU frequency scaling not supported
                                                                         [ ok ]
k@tt-z80k:~$ ls /sys/devices/system/cpu/cpu0/
crash_notes  topology
k@tt-z80k:~$ sudo mkdir /sys/devices/system/cpu/cpu0/cpufreq/
mkdir: cannot create directory `/sys/devices/system/cpu/cpu0/cpufreq/': Operation not permitted
k@tt-z80k:~$
k@tt-z80k:~$ uname -a
Linux tt-z80k 2.6.17-10-generic #2 SMP Fri Oct 13 15:34:39 UTC 2006 x86_64 GNU/Linux
k@tt-z80k:~$ more /proc/cpufreq
/proc/cpufreq: No such file or directory
k@tt-z80k:~$ more /proc/cpuinfo
processor       : 0
vendor_id       : AuthenticAMD
cpu family      : 15
model           : 4
model name      : AMD Athlon(tm) 64 Processor 3700+
stepping        : 10
cpu MHz         : 2393.851
cache size      : 1024 KB
fpu             : yes
fpu_exception   : yes
cpuid level     : 1
wp              : yes
flags           : fpu vme de pse tsc msr pae mce cx8 sep mtrr pge mca cmov pat pse36 clflush mmx fxsr sse 
sse2 syscall nx mmxext lm 3dnowext 3dnow up
bogomips        : 4790.73
TLB size        : 1024 4K pages
clflush size    : 64
cache_alignment : 64
address sizes   : 40 bits physical, 48 bits virtual
power management: ts fid vid ttp

k@tt-z80k:~$ lsmod | grep cpu
cpufreq_userspace       6560  0 
cpufreq_stats           9312  0 
freq_table              7104  1 cpufreq_stats
cpufreq_powersave       3456  0 
cpufreq_ondemand       10928  0 
cpufreq_conservative    11272  0 
k@tt-z80k:~$ modprobe powernow-k8
FATAL: Error inserting powernow_k8 (/lib/modules/2.6.17-10-generic/kernel/arch/x86_64/kernel/cpufreq/powernow-k8.ko): Operation not permitted
k@tt-z80k:~$ grep -i power /var/log/messages
May 31 11:33:56 tt-z80k kernel: [ 3725.267571] powernow-k8: Found 1 AMD Athlon 64 / Opteron processors (version 1.60.2)
May 31 11:36:05 tt-z80k kernel: [ 3853.632256] powernow-k8: Found 1 AMD Athlon 64 / Opteron processors (version 1.60.2)
May 31 15:12:36 tt-z80k kernel: [    5.640266] ACPI: Power Resource [GFAN] (off)
May 31 15:12:36 tt-z80k kernel: [   37.021556] ACPI: Power Button (FF) [PWRF]
May 31 15:12:36 tt-z80k kernel: [   37.021592] ACPI: Power Button (CM) [PWRB]
May 31 15:12:36 tt-z80k kernel: [   37.361502] powernow-k8: Found 1 AMD Athlon 64 / Opteron processors (version 1.60.2)
May 31 19:34:16 tt-z80k kernel: [   18.500242] ACPI: Power Resource [GFAN] (off)
May 31 19:34:16 tt-z80k kernel: [   49.534598] ACPI: Power Button (FF) [PWRF]
May 31 19:34:16 tt-z80k kernel: [   49.534633] ACPI: Power Button (CM) [PWRB]
May 31 19:34:16 tt-z80k kernel: [   49.873456] powernow-k8: Found 1 AMD Athlon 64 / Opteron processors (version 1.60.2)


Thanks...