newbie with a problem :)

Ok, here is the situation:
I have an office building in which everyone shares a T1 connection. The office suite that I am dealing with has their internet connection attached to an HP procurve switch 4000m with an IP address of 192,168.1.1 that it is getting from the DHCP router that the T1 is plugged into. This is a bad setup as all offices in the building are essentially on the same network. To solve this, I wanted to add a Linksys befsr81 router between the HP switch and the T1 line in order to create a private LAN. 1) Is this the right approach to take? 2) After putting the router in between, I was able to browse the entire network but could not get an internet connection. So not only did I not create the private LAN, I completely lost the internet connection! After googling around, it seems that I need the Linksys to lease out IP addresses on a separate subnet. (Which I don't think this model router can do) Is this correct? Would creating a VLAN using the switch (and not the router) be another alternative? Sorry for so many questions. Hopefully someone can help. Let me know if you need more information. Thanks in advance!