Why not replace the foam with a well-knit cover made from good yarn? Here's how.
NOTE: this Instructable assumes that you have a basic knowledge of knitting techniques: casting on, knit, purl, and increasing. If you don't, I recommend you spend some time perusing the Yarn section of Instructables, check out some knitting books from your library, or find some like-minded folks to help you get started.
Step 1: Materials
Yarn - the finest you can get. I used some fingering lambswool I recycled from a thrift store sweater (Great info on recycling sweaters is available here). It's okay to use pure wool, since this won't ever get washed. Sock yarn would be great.
Knitting Needles - smaller is better! I used my finest double-pointed set from KnitPicks: 2mm in diameter. You'll need four needles.
Sewing Needle (pictured at Step 5). This project has to be stitched shut, so a good needle is essential. Try to find a thin one with a blunt point and large eye, usually sold as "tapestry" needles.
Crochet Hook (optional, pictured at Step 3). With such small yarn and a tiny first loop, a good small hook can be helpful for casting on.
Step 2: Skin the Earbuds
Step 3: Cast On
Repeat with the second and third needles. You will have six stitches. Everything is very loose at this point. Don't worry, it will tighten up later. Do be careful not to drop a needle out of your stitches, though!
Step 4: Work Rounds
For each needle in the first increase round, I knit one, make one (that's the increase) and then knit one more. At the end of that round, I'll have a total of nine stitches. Knit one round plain, then another increase round (K1, M1, K to end per needle) for 12 stitches total.
TIP: on the plain rounds, give the yarn a little tug on the second stitch on each needle. This will compensate for the gaps that appear between needles. It's not really necessary on this tiny project, but it's a good habit to get into.
After a few rounds, turn the work over and pull the tail in the center to tighten up the knot and bring everything together. Work a couple more rounds and test for fit on your earbud. When you can stretch it so all three needles are on the back side of the 'bud, that's the right fit. For me, I got there when there were 18 stitches on my needles, but your mileage may vary.
Step 5: Bind Off and Stitch Up
Break or snip the original tail inside of your cover. Fit the little stocking cap over your earbud in a way that pleases you. Thread the working tail onto your needle, and stitch across the circle to a point about 1/3 of the way around. Continue stitching around the raised back of the earbud, inserting your needle about two stitches back from the tail's exit point. Then stitch around to two stitches behind stitch one. It's complicated to explain step-by-step, but think of the way you tighten lug nuts, or how you made five-pointed stars in kindergarten.
Work around until there's nowhere else to put your needle, pulling each stitch tight as you go. Then tie off with an overhand knot and hide your tail. Done!
Step 6: Second Verse, Same As the First.
UPDATE: I've added two new photos with other examples I've made. The black and grey ones are knit, and the blue and red are crocheted.