I notice you use relative addressing on your pages. This is not good, since one single mistake can "create" phantom directories or many pages in a directory that doesn't really exist.
Your initial problem was probably caused by a relative link to "catalog/Some-Page.html" (no leading "/") on a page that was already in the /catalog/ directory. This would have automatically created a link forward into a /catalog/catalog/ folder (as Google followed the link), and any relative links on those pages would also look like they were in /catalog/catalog/.
If it's not possible to use a fully-qualified link (that includes the domain name), at least create a link that is relative to the root directory; that is, with a leading "/" character. E.g.: href="/catalog/DIY-Supplies-p-1-c-251.html"
I don't know if this will help, or even provide any insight into what's happened re: Google's indexing but...
I noticed you have a homepage in the catalog folder at http://www.dizzidezine.com.au/catalog/home.php.
If there are relative links on the above home.php in the catalog folder that call the catalog subdirectory could that have created the /catalog/catalog/ links that Google is indexing?
Our own site is slightly outdated in terms of folder structure and we had to create a duplicate homepage inside one of the folders. This works fine (other than having to update two homepages instead of one when changes are made) but we have to be careful not to confuse the two pages. On the homepage in our root folder all the links are subdirectory/page.html, but on the second homepage in the actual folder we had to change the relative links to only page.html in order to avoid the link actually calling subdirectory/subdirectory/page.html
Hope that made some sort of sense, and hope you get it figured out soon!