Based on your description, you might look into the Split Polygons tool on the Topology toolbar. This allows you to use a line/polygon shapefile to chop up a polygon shapefile. You will need an ArcInfo license to run it. Also, be forewarned that if you are attempting to chop up lots of polygons with many vertices, it could take awhile to process or could hang/crash depending on your computer's hardware.
An alternative would be to use Feature to Polygon to convert the border/lines shapefile to polygons, and then Intersect with the other polygons layer to chop it up. Feature to Polygon does require an ArcInfo license. An alternative to Feature to Polygon is to install the ET GeoWizards Toolbar which has a Polylines to Polygons tool which does the same thing and is free and doesn't require an ArcInfo license.