Frozen Rune

I'm going to drop a preemptive comment. In patch 10.1.5, these are returning to the game. They are located in the boss rooms. Here's a list of where I found them, they COULD alternate OR they could have set spawn areas.

Spider/Arachnid Wing
Anub'Rekhan: Behind him and on the wall to his left. THIS CAN BE OBTAINED WITHOUT ATTACKING HIM.
Grand Widow Faerlina: Immediately left of her stage, before the stairs.
Maexxna: Far left "Corner" of the circular room, think between the 10:00 & 11:00 positions

Abomination/Construct Wing
Patchwerk: On the wall LEFT of the narrow hall with the slimes & where Patchwerk himself pats. THIS CAN BE OBTAINED WITHOUT ATTACKING HIM.
Grobbulus: To the left of the ramp going up. Original location changed from beta. There are two in his room, from the entrance it's in the alcove on the left behind the abomination giants, and one up the ramp on the first landing, against the wall, cannot miss it.
Gluth: Bottom right corner of his room. It'll be on your immediate right when you drop out of the pipe tunnel.
Thaddius: Left of where he stands on the circular part of the wall.

Death Knight/Military Wing
instructor Razuvious: From where you descend to fight him, it's on the left side of the circular room. Between the two dummies, his apprentices are training. THIS CAN BE OBTAINED WITHOUT ATTACKING HIM.
Gothik the Harvester: Opposite the wall side of the gate to leave the room, on the Dead Side. THIS CAN BE OBTAINED WITHOUT ATTACKING RAZUVIOUS! Gothik will not spawn so you cannot continue without killing Razuvious first.
The Four Horsemen: Looking at the Horsemen from the entrance, it's in the back left corner of the room. Look around all the edges, it's tucked away. There's also one in the bottom right corner if you're looking at the Horsemen.

Plague Wing
Noth the Plaguebringer: Looking at Noth, it's on a wall behind him near the center. THIS CAN BE OBTAINED WITHOUT ATTACKING HIM.
Heigen the Unclean: When you enter the room, it's on the immediate left near the elevated ground, easy to overlook. Turn the camera and you'll see it easily as soon as you enter the room. EDIT: There can be a second one on the immediate RIGHT side of his room as well.
Loatheb: Near the corner to the left of the teleporter to return to the center of Naxxramas. EDIT: A second is on the immediate left of entering this room in a corner, by the green grate.

Frostwrym Wing
Sapphirons Lair: Can't find it, will update you if informed or when I find it. **STILL NEED LOCATION IF ANYONE HAS FOUND IT** There are no Frozen Runes to collect.
Kel'Thuzad's Chamber: Cannot find it, will update you if informed or when I find it. **STILL NEED LOCATION IF ANYONE HAS FOUND IT** There are no Frozen Runes to Collect.

Hopefully, this helps out. As soon as I find out ways to get the missing patterns, expect me to post how I found them too. If needed, I will upload pictures of the locations for each rune.

Addendum: After testing this with 7 toons in two weeks, the Runes seem to appear in the same areas. They also respawn after an hour. All the Outer Ring Runes are OFF the beaten path to the bosses. You'll need to look behind the arches most of the time.

Arachnid Quarter (Outer Ring)
After Grand Widow: Behind the giant spider, look behind the Spiderwebs.
West of Maexxna's Nest: The first one is behind the first arch,
West of Maexxna's Nest: Second is at the bottom of the ramp, in the circular area.

Plague Quarter (Outer Ring)
Near The Necrotic Vault: Jump off the platform with the broken railing. You'll see one immediately on the left side of the Archway.
Outer Ring: Ahead of the previous one, it'll be in between two of the circular rooms. On the left wall, you'll see the rune.
Outer Ring (Noth's Room): The last one in the Plague Quarter is on a ledge that drops down to Noth's room. It'll be on the right. You will also find a page of Omarion's Second Notebook here if you do not have that and have already found his book.

Death Knight Quarter (Outer Ring)
Four Horseman Hall: Before going to face the Four Horsemen, the archway has one on the right.
Four Horseman Hall: After the one above, continue through the circular room and it's on the arch on the left.
Four Horseman Hall: Immediately behind the above rune is another.
Four Horseman Hall: Run all the way down the hall, past the Horsemen room, past were the other runes are found. This is just above the slime pool, at 40+ this shouldn't kill him. YOu can grab this without death or water walking.

Abomination Quarter (Outer Ring)
Right of the Halls of Reanimation: First circular room, on the arch heading downwards, you'll see it on the left.
Right of the Halls of Reanimation: Near the underwater passage to the Arachnid Quarter, it's on the arch on the right-hand side if you're heading down the ramp.
Left of the Halls of Reanimation: Immediately on the left of the arch where you turn to go down the ramp. It'll be behind you.
Left of the Halls of Reanimation: At the bottom of the ramp, on the left of the arch. It'll be behind you.

So all in all, I believe there are 29 runes per run. Keep in mind, that you can farm these every hour after you kill a boss. Just leave the instance for said hour and they'll respawn.

EDIT: They do NOT alternate locations. They are static in their locations.

EDIT 2: I've added notes of which ones can be obtained by not attacking a boss. So these CAN BE FARMED, which means you can get at least 5 runes before having to leave Naxxramas and resetting all dungeons/raids.

EDIT 3: So, Thanks to Moirine and Drozee, there are ADDITIONAL spawn points. I found two in Grobbulus' room, one on the immediate left behind the two abominations and one on the ramp going upstairs. There's a LOT in the Outer Rings between bosses. So be sure to look around corners, on walls, and go to areas that are off the beaten path. More than the ones in the boss rooms can be found. Do not worry about swimming in the ooze between sections that connect, there are no Frozen Runes underwater, if someone finds any please inform me. There can also be some more that spawn in Boss rooms such as Heigen the Uncleans, I found Frozen Runes on BOTH sides of the doorway you enter his room. One on the immediate left & right. The original post has been updated

EDIT 4: THESE WILL RESPAWN! So I cleared several bosses, and needed to farm some more Invader's Scourgestone from Stratholme, came back today and found THEY DO RESPAWN. Blizzard wanted these to be VERY farmable, thank you very much.

EDIT 5: Fixed errors.

EDIT 6: My next edit SHOULD include the locations of other Frozen Runes I've found while exploring Naxxramas.

EDIT 7: Added more runes I've found or were told there are.

EDIT 8: Added more runes that were not accounted for. Thanks for the maps & letting me know where you found them boys. All 31 are accounted for. I do not think there will be anymore updates.

All frozen runes in Naxxramas located here (31 total)

Map
https://www.wowhead.com/maps?data=3456.5:723787577771553746635626650626748591784532807532757090470235504328397237253105591167634132705323341431324247310359299513285657284672333730283773293880464674451171395134534243621245367657

This item is no longer in the game. They were attained from inside level 60 Naxxramas which no longer exists.

They were used for profession craft able frost resistance gear as mentioned above. They were also used in the quest http://www.wowhead.com/?item=22707 for an epic frost resistance ring. Also no longer attainable.

Could be called a "collector" item. Still have quite a few stockpiled on my banks.