> It would be very hard to tell that story in fantasy.

Perhaps Steampunk is closer to this, given that "steam" was part of the first industrial revolution.

However there are some interesting ideas floating around that you could use to tell a pure-Fantasy cyberpunk story; I'm sure someone's tried a novel, but I am only familiar with the tabletop RPG http://cryptorpg.com/, where magic enables cryptography and messaging. From there you can recapitulate pretty much all of the dystopian power/narrative structures that make Cyberpunk what it is.

Magic-as-technology is a surprisingly under-explored concept, with the right magic system I think you could easily tell a Cyberpunk story.