SOLUTION:
After upgrading my production server running Ubuntu 8.04 to 10.04, all my internal links of WordPress were broken.
A quick fix in the settings, sets everything right.
Settings > Permalinks > Changed ours from "Custom" setting to "Default" and JoyJoy. . . links worked again.