It's not unusual to see people "fake" double spacing in Word docs by hitting the enter key twice at every line break. Turn on hidden characters to see if that's what's going on, and if it is, you have a bit of work cut out for you.
First, you'll need to identify the real paragraph ends and insert some random character to use as a marker. Use something that will not appear anywhere else in the story, some fancy bullet or something.
Next, open find/change and enter ^p in the find field, and leave the change field blank, then change all, which is going to remove all paragraph breaks (and any style changes along with them).
Now enter the random character you added to mark the paragraph ends in the find field, and ^p in the change field, and change all, and you'll have real paragraphs ready for formatting.
If Dave is watching (or someone else with GREP skills) there might be a way using GREP to do this a bit cleaner, but my guess would be if you've got a word doc with all those line breaks it wasn't styled anyway. :)
Peter