Given more information in your latest comment it seems like your problem isn't related to Drupal at all, it's just the way you structure your href attribute.
This might be down to literally omitting the starting
/ in your href attribute. Without the starting
/ the link is assumed to be relative to the current page!
With the starting
/ the link is assumed to be relative to the baseurl.
Since you're planning on showing the link on many different pages, you can't use URL that is relative to the current page, you have to use the URL that is relative to the domain name:
<a href="/fr/page-in-french">, and not:
The way you describe it in your latest comment, that links turn out correctly on all pages except from the front page, is only a coincidence. You obviously don't have any deeper links (
/fr/first/second), you only have one level after the lang (
/fr/first). On the "one level pages" your link is evaluated to be relative to that page:
On a page with deeper path structure your link would evaluate to:
/fr/first/your-link. Which doesn't exist and you don't want that ;)
You must use the starting
/ in your href attributes if you want your link to always be relative to the baseurl, and not to the page you're currently viewing.
When you structure your href to
/fr/page-in-french the links will always be correct, no matter which page they're displayed on.
But it also means the link will always link to the French interface and the French node. Even on English pages with English interface.
If you expect to use that same block on all languages, and you expect to display related language links (if on a French page show link to French node with
/fr/, if on an English page show link to English node without the lang code), then you need to use the Multilink module, as I described in my previous answer.
Another option is to create different blocks (or Translate the existing block) so different blocks/translations are shown on different languages. This is a good solution if you don't have a lot of links. You'd have to manually writeup all the links correctly for all the languages (all English links in English block, then separately all French links with
/fr/ in French block), and check them all. So it's doable if you don't have a lot of links and languages.
For all other cases I'd recommend Multilink module as the only sensible solution.