So after much determination I figured out how to get permalinks working with my hosting provider (Netfirms). Originally, permalinks were working, but when coming back to the site at a later point all clicks just showed my home page. I tried to retrace my steps to determine what I had done to create the little botch up.

I uninstalled some plugins, made a few changes, but a friend hinted to me that it could be something to do with my mod_rewrite, or basically hosting related. That flicked a switch in my head and I remembered that I switched from PHP version 4 to 5.

After much searching I came accross teh following site: http://www.joelika.com/2006/10/31/253. Through some additional trials I determined that by adding the following line ($match = ‘index.php/’.$match;) after the following line (foreach ($rewrite as $match => $query) {) in the /wp-includes/classes.php, permalinks worked again.