1st, thank you for this great plugins :).
I'm facing the exact same problem with stephenwayne in this post http://wordpress.org/support/topic/plugin-promotion-slider-promotion-pages-not-found-when-using-custom-permalinks?replies=2.
Fyi, I'm using WP 3.2.1 and Promo Slider 3.3.1.
I have tries using the default theme and disabling all other plugins as suggested but the problem still exist.
Please help. Thank you.