Entre Belgique et France en général, pas plus qu'entre un Marseillais et un Parisien. C'est une question d'accents et de ce qu'on appelle les régionalismes (des mots ou expressions qui ne se disent pas en français "standard" mais bien dans certaines régions). Mais nous parlons bien la même langue. Peut-être que la fille française était de Marseille ?
En Belgique, nous avons trois langues officielles : le français, le néerlandais et l'allemand. Il y a par exemple beaucoup de Belges néerlandophones qui parlent très bien le français, mais ils ont forcément aussi un accent différent.
Je dirais que pour quelqu'un qui apprend le français "standard", les plus difficiles à comprendre seraient les Québecois (mais je connais très peu les français de l'Afrique). Ils ont leurs propres expressions et tournures de phrase, et leur accent est très différent de celui des Européens. Mais ils sont très accueillants donc ça se surmonte très vite