Permalinks Work, But Don’t

Ok, I’m not really sure what’s going on with my permalinks here. When I set them to something like “/%year%/%monthnum%/%day%/%postname%/”, they don’t work. However, they do when I do “/index.php/”. I’m on an apache server. I have another instance installed on this server and it works just fine there. I’ve deleted the .htacess file and had it re-write it. Thoughts?