Permalink Problems or Bug

Please can anyone help? I seem to have some sort of bug in my permalinks. Whilst the main blog page will display, all internal links within the page, such as categories and archives are brocken, they divert to 404 error.

I’ve tried to find a solution in the WP forums and it seems I need to make changes to my permalinks, however, if I access the permalinks area of the admin pages, the whole blog, even the main page goes to 404 error and I have to re-upload it to get the main page to work again, this however does not fix the links.

With the permalink section of the admin pages, I literally just go in there, I don’t even need to change anything and the problem occurs.

Any help would be much appreciated.