Draconis said everything there is to say about the loss of the *kʷ AFAIK, but I spent €250 on an etymological dictionary of Latin a while back so I want to expand on the -bi part.
According to De Vaan's Etymological Dictionary of Latin and the other Italic languages, ubī can theoretically reflect either *kʷubʰei or *kʷudʰei. *-bʰi would be a PIE instrumental ending, whereas *-dʰei would be an Italic innovation for *kʷudʰe 'where', which is reflected in Indo-Iranian (Skt. kúha, OAv. kudā 'where') and Slavic (kьde 'whenever, anywhere'). In view of the latter correspondence, De Vaan considers a Proto-Italic preform *kʷuþei to be more likely (I don't think *kʷu would still be *kʷu in Proto-Italic, though; the boukólos rule should have eliminated the labialisation earlier than that). He finally notes that Hittite ku-wa-pi 'where, when' is attested, which reflects PIE *kʷó-bʰi (that is, with the instrumental ending).
De Vaan doesn't mention it, but *-dʰe ~ -dʰi is a locative particle reflected in Greek as -θε or -θι, as Draconis mentioned, which shows up e.g. in Greek πόθι 'where' (which, however, has *kʷos in the o-grade, like the Hittite; PIE *bʰ would have become Gk. φ, though, so it can't continue the instrumental).
The Sabellic languages do have attested cognates of ubi, with the expected p at the front: Oscan puf and Umbrian pufe. Like the Latin, they could theoretically reflect either *kʷubʰei or *kʷudʰei.
(Annoyingly, the disappearance of the initial c- in Latin isn't even remarked on.)
