[Haskell-beginners] Help with slow algorithm

[Diego Echeverri]

Hi guys.

I've been playing with https://www.spoj.pl/ to get better with Haskell.
I'm trying to do: https://www.spoj.pl/problems/PALIN/

Basically given a number k, you have to find a number bigger than k
that is palindrome. The thing is that k can be 1000000 digits long.

I have learnt a bunch of things doing this exercise but I'm still
getting time-limit exception.

Here's the code: http://gist.github.com/401880

I believe that the bottleneck is in the addOne function (Specially in
the case where you have a bunch of nines). I have rewritten it to use
STArray but isn't fast enough.
doing: addOne $ B.replicate 500000 'a' takes too much time!

Can anybody point me out of better (faster) ways to improve the code?
I don't need my code fixed, just suggestions and clues about things to
try.

Thanks!
Diego Echeverri