There were two drivers on the site, a French one (the 8/35 suggesting it might have the France-only vpi/vci settings) and an international. Which one did you use? There is a driver on Sagem's UK support site now anyway.
My French one (I live in France) worked. After the installation and restart I opened up Network Preferences, put in the account name and password under the PPP tab, clicked Apply Now and it worked immediately.
It would be better if you could get the ethernet router to work and I'm surprised that you got the same message. For starters I thought that came from Internet Connect when it tries to connect you and failed, but with a router it handles the connection for you and you don't need Internet Connect.
In my limited experience you just point your browser (IE tending to be compatible) with an address of something like
http://168.192.1.1 to get the set up page, set up the UK settings (PPPoA, vpi/vci 0/38, VC multiplexing, I believe) with your account details and you're away. Or at least that's the theory... What router is it?
Mark