AFAIK there are 3 timers on the Atmega328. Two 8-bit, and one 16-bit. Each timer has two output compare registers, so you can indeed have 6x 8-bit PWM running. As each timer has two PWM outputs, they aren't completely independent because each pair has to have the same period, and only one pair can be >8-bit resolution.
As for getting 25kHz PWM frequency, yes, I imagine one would need an odd crystal/oscillator to get it given the 2^n nature of the prescalers. A 12.288MHz or 6.144MHz xtal/osc are common values used for digital audio, that divided by 256 can give 24kHz. So for 12,288MHz a prescaler of 2 is required for 24kHz 8-bit PWM.
If you really require 25kHz then you can set your TOP value of the timer to be something other than 255. This means your PWM resolution will be <8 bit, and will be fractional, which makes life a bit difficult if you require precision.