That said one must still overpower the ambient light for this to work. And it is true depending on the flash duration. The SB-800s have a max duration of 1/1000th but my camera can go faster than that. Mind you it's not like at 1/8000th I can get a full blast from the flash. The strobe effect in auto FP mode takes a bit of power from the flash.
You need to set your camera's max sync speed in it's custom menu somewhere. Check the manual for where but I guess the option will be somewhere under the Ds. It's Max Flash Sync Speed, and set it to 1/250th Auto-FP. The flash should show FP on it's display and it stops blocking your shutter speed.