Lion has offices all over Taiwan. If they say they cannot do it, it is really because they cannot do it. Mostly, I am very pleased with their services as they are on the ball.
If you go to to Taipei Main Station, there are a myriad of kiosks on the main foyer. EZTravel is also a big one, try them.
Depending on your destination, a B&B might be a better choice if hotels are all booked. Airbnb time, perhaps? There are really cool choices out there, and if you have transportation overed by the travel agency, an Airbnb place is more relaiable than a usual B&B, unless it is a long standing one. My
If you are going to Taitung -envy you!- then definetively try to get air ticket or train ticket through agency, maybe book a tour, but a B&B will be more enjoyable and economical.