I'm not sure either lifted it from the other. The concept was around with third-party apps for XP and built into Vista, but it's a feature that's gotten so ubiquitous (spotlight, unity dash, windows search) that it's difficult to say who came up with it first, if anyone did.
I'd be curious to see if they lifted this from Ubuntu, or the other way around.
It's a bit of an adjustment, but after a couple of days of usage opening a Run dialog just feels so primitive.