Indeed yours looks like the ones that yen_saw shared a photo of (linked to below), and looks a little smoke or cherry bomb. I would have never guessed it was a mantid ooth. A good catch by mantiseater, as it appears it explains the unknown ooths and perhaps your nymphs too.Looking at this post: could my weird little things in the ootheca picture be liturgusa ootheca?? Should I start ordering springtails just in case? And that means that the liturgusa are now breeding in south florida, which I assume isn't good. I wonder how the heck they got here.
EDIT: where did the link go? http://mantidforum.net/forums/index.php?showtopic=9777&hl=liturgusa#entry56360
In regards to how they got to Florida, there are a few ways - stowaways with freight/boats, a travelers unknown souvenir/hitchhiker, released by a irresponsible mantid keeper, introduced as a pest control back in the early 20th century in limited numbers, or naturally found their way (most unlikely). Seems to be a trend lately, as there are at least one mantid in California lately too that shouldn't be there.