Your mention about the artboards put me on a hunch. I am using CS5, but all the artworks are on the artboard. So I saved it down to CS2 as you suggested. It fixed the problem. Saving it back up to CS5 made no difference and I can now add strokes without breaking anything.
I still do not know what caused the problem. I might raise the problem with Adobe themselves one day, but it’s not that serious.
Thanks!