(must be frank here - I knew the answer before posting, just didn't know how to load this data to StackOverflow. Thought the solution I found was valuable for others, so wanted to post it here. I'm new here, so please no harsh critics :) )
So eventually the problem resulted from, AFAICT, a change in behavior in the OS.
As stated the tint code worked before the upgrade and was written like this:
// Toolbar content
NSArray *items=[NSArray arrayWithObjects: ... ]; // PSEUDO CODE HERE
[toolbar setItems:items];
// Add tint
toolbar.tintColor = [UIColor colorWithRed:0.83 green:0.43 blue:0.57 alpha:0.5];
What I needed to do, was just reverse the order of things:
// Add tint
toolbar.tintColor = [UIColor colorWithRed:0.83 green:0.43 blue:0.57 alpha:0.5];
// Toolbar content
NSArray *items=[NSArray arrayWithObjects: ... ]; // PSEUDO CODE HERE
[toolbar setItems:items];
(If you created UIToolbar in Interface Builder, you can change it's tint there, and that applies for the buttons as well).
I guess the tint updated all buttons before iOS 4, while in iOS 4 it doesn't and when adding buttons, they check for existing tint. But this is just a guess. The solution works anyhow..
Hope this helps someone, and that I didn't violate any sacred SO rules...
Cheers!