previous_post_link always show the same post link

I have a strange problem with previous_post_link and next_post_link. If I put the code in the top of the sidebars it works ok, but if I put it after all the sidebars it always show the same posts links instead the previous and next posts links. Any ideas? Thanks!