Up until the release of this trailer, Bioshock: Infinite was known as project Icarus. 
 
Now if you research Icarus here:  http://en.wikipedia.org/wiki/Icarus 
 
Icarus is a Greek myth about a man who made wings to fly, but flew too close to the son and fell to his death.   
 
This links with the idea of the sky city and the concepts put in Bioshock about how humanity is going too far and how industrialists are evil.  So I suppose that's how Bioshock could come into it because they may be about the same underling problem, but Infinite may not be directly linked to the original.

I feel like an absolute ass for doing this but.....duh.

Judging by the interviews Ken Levine has been giving, I don't think the BioShock name refers to a certain type of story or mortif. I mean, that's part of it, with the whole "city / utopia gone wrong" idea, but I think it's more related to the framework and mechanics of the games they enjoy making. Their brand of a story-driven FPS.
 
Also, I think a lot of the surprise came from the fact that it was a BioShock game, rather than the relation to Icarus and it being set in the sky. A lot of the vibe that Irrational gave off prior to the big reveal was that it would be something totally removed from their previous games. In fact, I remember the Take-Two president saying earlier this year that part of the reason 2K Marin did BioShock 2 was because Irrational wanted to be free to work on "an original title that could become another franchise". Another BioShock game seems to be contradictory to that.

It was obvious?  If it was, everybody would have been calling it before the reveal.  Not many of us would have guessed it was another Bioshock game, like Fjordson said. 
 
And yeah, that's not really the reasoning behind the Bioshock "brand".  Ken Levine actually compared the name "Bioshock" to "Final Fantasy" in a recent interview.

Duh 
 
Really, it was obvious it was gonna be something to do with the sky, the question was whether it was Bioshock or not. Everyone and their mother knows who Icarus is. 

I guessed it was something to do with the air but I didn't guess that it was another BioShock game.

I'm still wondering if it'll be set in the same way. I find his "I don't think that's a constructive conversation to be having" a little cryptic.

Hindsight is 20/20.

" I feel like an absolute ass for doing this but.....duh. "

To be fair, you couldn't really guess it was going to be a Bioshock game, because they said it wasn't.  That obviously changed late on for marketing reasons.
 
The 'Bioshock in the sky' thing seemed fairly likely, I just assumed it would have a new name.

I thought it was going to be a flying game, myself, maybe something like Crimson Skies.

Like how they used "Beyond the Sea" in advertisements for Bioshock, I'm waiting for them to use B.O.B's "I'll Be In The Sky" for Bioshock: Infinite.

Derp.

" Like how they used "Beyond the Sea" in advertisements for Bioshock "

"Not many of us would have guessed it was another Bioshock game."

" @FluxWaveZ said:

"Not many of us would have guessed it was another Bioshock game."

This. Although as has been mentioned before the Giant Bomb staff did start joking about a Bioshock in the sky before it was revealed what Project Icarus was. "

I don't know about all that,but I'm looking forward to see how this game comes along.
I hope it's original,and not just Bioshock 1 in the air.I mean I hope the story isn't the exact same thing but only with a few tweaks or something.