I too had this same problem with my Li 1718. I used the Hard Disk Based Recovery system provided by Fujitsu Siemens and my FirstSteps is running fine as long as I right click on the icon and select "Run as administrator". The process to use the HDBR on this Amilo is as follows:
Upon system startup, when Fujitsu Siemens Computer logo displays, press and hold F8. A menu screen will appear. Choose "Repair your system", the log in with your name and password that you would normally use when you log on. Then another menu shall appear, choose the Fujitsu Siemens recovery option. The recovery process will start and took me around 10 minutes to complete. WARNING! ALL PERSONAL DATA WILL BE ERASED!
After this, the computer goes back as thought it had just been bought and all the software at original purchase, (including FirstSteps) will be there! The recovery went with no problems for me, although i had to delete the ISP folder in C: as it was stopping my wireless networking from working. Good luck with this, and I would highly recommend it if you want FirstSteps to work again, or if you just want the delievery state of the laptop! Thanks Matt!