Not sure whether you made a declension mistake or whether you're great at puns: "butelka winy" is "a bottle of guilt" ;)
Well, the sentence makes probably more sense if the bottle was emptied very recently, if you find such bottle in your cellar, it's not exactly 'butelka wina' anymore but more of 'butelka po winie'.
Dunno how to translate it, but a construction 'X po Y' is the one you use in such situation, when X used to 'own' Y or have it inside: słoik po dżemie (a jar which used to have jam in it), zegarek po dziadku (a watch which used to belong to grandpa), pudełko po telewizorze (the box in which your TV set arrived), etc. Y is then in Instrumental.
There isn't any. Anyway, both work, I asked a British native about which one's better, she said that to her "a bottle of wine has wine in it, whereas a wine bottle is the bottle itself, irrespective of whether or not there's anything in it." Well, this seems to suit the Polish sentence. Which also seems a little bit strange to me, frankly.