I'd say that it's probably not an idiom but it's a grey area (which itself is an idiom). Generally, an idiom's meaning isn't obvious. But how do we define "obvious"?
One way would be to do a poll, asking 100 people who weren't familiar with the phrase to guess its meaning. I'd say that if the majority of people don't guess it, then it's an idiom. If they do guess it, then it's just a figure of speech (all idioms are also figures of speech, which just means something that isn't meant to be taken literally).
Having agreed on this, we could then start arguing about what consitutes a majority - does 51% count? That seems too low to me. My instinct would be that an idiom wouldn't be guessed by at least 75% of people.
Going on that, my own guess would be that more than 25% of people would guess the correct meaning for "The middle of nowhere", (therefore less than 75% failing to guess it) and so it would fail the idiom test. But there's a lot of guessing and opinion in there - hence why I described it as a "grey area".