It is possible to get the exact 250nsec/1000nsec timings that are required by the WS2811 out of a 16MHz AVR, with no timing jitter anywhere. It's just not particularly easy, you need to do it in assembler. I've written it up, along with code, at http://bleaklow.com/2012/12/02/driving_the_ws2811_at_800khz_with_a_16mhz_avr.html. Note this code is for pixels wired up in (G,R,B) order rather than (R,G,B).
And another note: there seems to be an assumption in earlier posts on this thread that if you use the FastSPI library to drive the WS2811 you are using SPI and therefore the WS2811 is a SPI device. That's wrong - when driving the WS2811 FastSPI uses bit-banging. Oh, and the timings aren't correct, which may be the issue if it doesn't work for you - see the blog post linked to above for details.