When attempting to run spell-check on LibreOffice 4.1.0.4 on Fedora 19 I hit the F7 key and Spell Check launches and immediately says spellcheck complete. No it idn't.

Going into Tools => Options => Language Settings  and having a play didn't help.

So I did the following

yum install aspell-en # still didn't help
yum install hunspell # was already installed

# this did the trick
yum install hunspell-en 

# also make sure the language pack is
# installed
yum install libreoffice-langpack-en.x86_64

Restart all instances of LibreOffice

Then went into Tools => Options... => Language Settings and selected "English (Australia)" as shown below. You can tell you are on a winner because a little tick is on the left of the language you want.

Nek Minute.

And Houston we have a solution