Arquivos .a também são bibliotecas. A diferença é que .so são bibliotecas para linkagem dinâmica enquanto que .a são biblioteca para linkagem estática.
Esperimenta o comando
gcc -o teste -L/home/almodenah/Downloads teste.cpp libsmile.a
Se bem que "-lsmile" deveria funcionar também.
Pode ser que essa biblioteca tenha sido compilada para uma outra plataforma (para 64 bits e vc usa 32 bits, por exemplo), ou com uma versão diferente do gcc e com incompatibilidade binária com a versão que vc está tentando compilar, etc.
Se você tiver os fontes dessa biblioteca você pode tentar compilá-la vc mesmo. Assim deve dar certo.
Uma dica para identificar problemas: se o gcc compilou tudo, mas deu erros de referência indefinida para alguma função, quer dizer que o problema é na linkagem (faltou linkar com alguma biblioteca, ou não conseguiu linkar com as que vc tentou, etc). Se no entanto ele nem compilou e reclamou que não achou um cabeçalho .h ou não conhece uma certa função, como foi no caso do erro "erro fatal: smile.h: Arquivo ou diretório não encontrado" aí normalmente é indicar para o compilador onde (em que pasta) encontrar o cabeçalho que falta e/ou dar um "#include cabeçalho.h" que vc esqueceu. No caso do C++ pode ser também o namespace que vc esqueceu de especificar e ele também não encontra uma função.