If you change your permalinks from default to something else, and it gives you a 404 error. Chances are the rewrite module in apache2 is not enabled. I´m not sure how to do this on a windows server. On Debian variants and Red Hat variants you only need to pass one command via console and restart. It might be the same for many other Linux distros.
As root or sudo
That´s it. Then you need to restart your apache server.
service apache2 restart
Voila, your permalinks now works.