Magento – Where magento stores custom options for the products added to cart

It looks like your problem is on the product page, not in the cart. In order to add option data that page needs to submit a form, but the Add to Cart button is just doing a redirect on click

onclick="setLocation('http://paperhug.instantwebsitecloud.com/index.php/checkout/cart/add/uenc/aHR0cDovL3BhcGVyaHVnLmluc3RhbnR3ZWJzaXRlY2xvdWQuY29tL2luZGV4LnBocC9ncmVldGluZy1jYXJkcy9tb3RoZXJzLWRheS8xLWhvdXItZ3JlZXRpbmctY2FyZHMuaHRtbA,,/product/2/')"

should be:

onclick="productAddToCartForm.submit(this)"

It may have gotten changed when you were working on the add to cart buttons for the category pages.

Interesting question. I suggest doing it not by adding "Update" button to each items but using generic Magento "Update Cart" routine.

In this case we can assume that values of your drop-downs will be submitted with the form. Then you can observe checkout_cart_update_items_after event, get updated options with Mage::app()->getFrontController()->getRequest()->getParam(...) and change the selected option of each item.

This is just my theoretical assumptions but I'm sure you were not expecting complete code. Otherwise there's a commercial extension out there which is doing exactly what you need.