Cheap dimmers are cheap for a reason
Cheap dimmers often omit the extra parts needed to generate clean output, without EMI, asymmetric waveforms, or other things that can confuse the fiddly business involved in getting a LED to dim solely off a phase-controlled 120VAC power input.
Get a decent spec-grade dimmer intended for LED/CFL use (Lutron makes good stuff, and their support is solid too, if you want a brand name to go by) instead of the builder-grade cheapie you threw in there if the problem persists with dimmable bulbs. An air-gap shutoff is a good idea as well (all the Lutron dimmers have it, and any spec-grade dimmer should have it).
And make sure your bulbs are dimmable, too
LED drivers, whether integral or external, have to explicitly support phase-control dimming in order for it to work -- it will not work properly "by accident" as you found out the hard way. So, lesson learned: make sure your bulbs are dimmable when you're using them on an LED compatible dimmer.