This is an old post but I just want to thank you. I spent hours pulling my hair out trying to get my permalinks to work on something other than the default setting. I was thinking I made some critical error while switching servers and ended up reinstalling wordpress several times before finding out that GoDaddy was causing all my permalink problems.
I have a deluxe account so I knew I should have access to the mod-write feature and I was going crazy.
I went to sleep and when I woke up the links were working fine. Thank you!