That's where testing comes into play. If on the site it's for things are fine -- don't worry about it.
There's this habit of saying "NEVER USE THOSE" just because it's slow on one site -- what's slow on one could be blazingly fast on another -- that's CSS in a nutshell; what works in one place isn't necessarily good in another.
CSS3 gradients is a great example -- you use it once or twice on small elements with no extra effects attached, it's fine. You layer three or four of them with alpha transparency, rounded corners and box-shadows, and just trying to scroll the page in gecko becomes a painful affair (especially as the redraw takes so long you can see it "flash" on and off even on a i7)
Some of the ones listed I don't see there being issues with... :first-child and :last-child for example should have static-trips for targeting inside the browser. Those shouldn't be any slower than using classes. As a programmer, I would actually expect them to be FASTER than a class -- classes have to be tested against every element or a list of elements with that class (depending on the implementation). first and last should already exist in the DOM as pointers! You've grabbed the parent element, it should already HAVE pointers to first-child and last-child... otherwise how would it know what it's first child is or where to add new ones?!?
Others, like sibling selectors... I kind-of feel like they just make things more complicated than they need to be... BUT they shouldn't take any more or less time than descendant selectors -- parsing a chained list vs parsing a list of children -- net change zero!
In a lot of ways though, the talk about browser rendering speed on things like selectors ends up a bit like the Anti-table mafia's arguments about the "speed of rendering tables"... if a 386/40 running IE4 on Win 3.1 could handle a table, it's a BS thing to worry about when the average handheld has a 600mhz to 1ghz processor... and a $200 nettop is at 1.6ghz with hyperthreading.
Selectors should be much the same thing -- that Google page falls into that category on everything except :hover... and that's actually NOT because it slows the initial page render, but because it takes time to render the state change -- which means for small changes it's fine; major changes with giant slabs of content -- probably not so much.
As with anything else, it's more about what you're using it for than actually "using it or not using it".