I guess it depends on what made them uncomfortable. Was it the material? the shape? I know that the E-A-R classic yellow foamies come in 3 different sizes, standard + large + small. I always just get the standard ones but maybe you'd want to try the small ones to see if they are more comfortable.
These guys offer a "try-em-all" pack of 28 different types/sizes of foam earplugs for $15. Once you find which ones you like, then just order a big-ass box of those.
http://earplugstore.stores.yahoo.net/unfoamtrialp.html