I have a configurable product setup which has single products as colours, however I now wish to add a new attribute (e.g. size) to the product. I know that when you create a new product and select Configurable Product it lets you choose the attributes to associate, however I can't see an option to add more to an existing product.
Simple answer: You can't add additional "super" attributes later.
But: You can add it in the database. Have a look at the database table "catalog_product_super_attribute". If you know the product ID and the attribute ID (you can get them from the URLs when editing the specific product / attribute), you can add a new row there directly.