A theme has near complete control over the appearance of a site, including the widgets. And any plugin could load a stylesheet that overrides elements of your, intentionally or not. There are guidelines to encourage certain standards of code quality, which are enforced to some degree if the plugin/theme is hosted on the WordPress.org plugin repo, but there are no guidelines, much less enforced ones, for how the theme should look. (Would you want that?)
The best you can do is code the widget very generically, and minimally, so that the theme can take over. If you’d written a particular color scheme into the widget that was probably a mistake. It is just about guaranteed to clash with some themes.
You may think about providing multiple color schemes, but I’d just leave it to the theme.
To think about it slightly more abstractly, WordPress adds a number of IDs and classes to the sidebar and widget. A decent theme should use those to alter the display of the widget. You can add your own IDs and classes but most themes won’t know about them and so won’t use them. You can use those to try to force some styling but again, you are bound to clash with something.
It is the nature of the beast. I love WordPress for its extensibility, but that brings along certain issues. If the structure of the site were more rigidly controlled these things would be easier dealt with, but then, I wouldn’t be using WordPress. It would be to restrictive.