While I do not believe there is a strict canon explanation for why things are such, I have typically 'bought it' under the idea that each world, having achieved warp technology of its own accord by different methods and with entirely different sets of materials initially at their disposal, and presumably before the advent of push-button replicator technology to simply ask the computer for adamantium starships, were each simply a natural extension of their homeworld's natural and artificial resources.
In our own 21st century, space vessels are made of (among other things) titanium and aluminum - because they are both light-weight and dependable, but also because that's what we can make them out of. Aluminum is the third most abundant element found in the Earth's crust; titanium is the ninth-most. Were the availability different, perhaps we would have taken other routes altogether.
So, for Klingons and Romulans, it may well be that alloys which are green happen to be the metals they're most familiar with. They have a history of creating such ships from these metals; they know them and can work with them in a more efficient way than they would a metal from our world.
By the time the 24th century rolls around and we all know about each other, have blown each other's ships up, made friends and enemies and so on, perhaps one would expect civilizations to say, "Ah! Lousy Breen; no wonder their ships are so durable, they're made of ___ium. We should totally make our next Birds-of-Prey out of this __ium, this is going to be awesome." However, tradition can often offset adoption, in particular if your race is less focused on what the ship is actually made of and more focused on, say, interplanetary nationalism? Klingons and Romulans are pretty well-known for their reluctance to adopt off-world ideals and practices. A Klingon Bird-of-Prey built of duranium and tritanium (the Federation metals of choice, last I checked) might be seen as taboo, or at least, 'non-Klingon'.
One might expect the Romulans to know better, but then again there's always the possibility that green > grey. To that end, it may just be that whatever funny-named metals line the ships in Star Trek have their own set of trade-offs; for example, perhaps Federation ships are made of duranium because they happen to work well with our models for structural integrity fields. Meanwhile a different world with divergent but similar technology uses broccollium because their structural integrity fields work best in that setting.