you would also like Amon Tobin (he did an ost for a splinter cell game recently), he's got some nice instrumental hip hoppy stuff too back in some younger cd's
also in a very similar vein as DJ Shadow, this new guy from ninjatune popped up recently (altho apparently he's been mixing stuff for people under a real name), Blockhead, might have mentioned it before.
I've only listened to a little bit of Amon Tobin, but what I have listened to is amazing.
I haven't found much of Blockhead, but that video you linked to was pretty good, so I'll keep an eye out.