According to the definitions laid out here http://en.wikipedia.org/wiki/English_prefixes:
prefix description example
de- reverse action, get rid of deemphasise
un- reverse action, ... release from undo, untie
For this reason, both are semantically valid, since both prefixes state that the verb is to be reversed, but 'un-' makes more sense, because an "unbricked" object has been "released" from its state of being "bricked", i.e. broken - which makes a bit more sense than "getting rid of the 'brickedness'" that de- would imply.
There's no canonical answer here, because the usage of "brick" as a verb meaning "to break" is very modern (and hence somewhat unstandardized) word - and unbrick and debrick are even less standardized (my spell checker recognizes neither of them), but we can always look at actual usage to see which form has "stuck".
A quick search on Google suggests that "debrick phone" has roughly 357 pages compared with 19000 or so pages for "unbrick phone".
This means that "debrick" is less commonly used than "unbrick" - but it also means that neither are commonly used words at all.
This means that although neither of the words are Standard English (and hence neither are words I would use to advertise my business, or write in formal letters and emails), "unbrick" is the "more correct" of the two words.
Wiktionary and glosbe also both have entries for "unbrick" and not for "debrick", both mentioning its slang use to mean "restore to working order, after previously being inoperable".