Cheap sleeps in Tokyo?

Hi,
I am a travel writer/journalist travelling to Tokyo in October. I am going to write about 'visiting Tokyo on a budget'. I am considering staying a night in a capsule hotel, but not sure if I can find one that accepts women AND offers secure luggage storage for a suitcase.

So I am also looking for other suggestions for cheap places to stay. Preferably not a backpackers' hostel, but I wouldn't rule it out. I'd be keen to hear of anyone's specific suggestions, or something a little unusual. Maybe a minshuku??
Any ideas and suggestions most welcome please. If referring to a website - I cannot read Japanese.... only speak a very little of the language.
Thanks in advance!
Sarah

Have you seen this page?

http://www.japan-guide.com/e/e2028.html

Heaps of budget options here including a number of capsule hotels:-
http://www.hostelworld.com/

Various budget suggestions on pages like this:-
http://wikitravel.org/en/Tokyo/Taito#Budget
http://wikitravel.org/en/Tokyo/Asakusa#Budget_2

Manga-kissa/internet cafes are another option.

Enjoy your trip!

Contrary to all the horror stories of how expensive Japan is, you can find moderately priced places in Japan - even in Tokyo.
Two cheaper hotel chains across Japan are the
Toyoko Inn - www.toyoko-inn.com/eng/
and
Superhotel - www.superhoteljapan.com/en/

There is a whole collection of others at
http://www.wix.com/astroflight/accommodations

A few others worth mentioning are:
www.juyoh.co.jp/
www.newkoyo.com
www.sakura-hotel.co.jp
www.shrek-watta-house.com
www.first-cabin.jp/en/
And if you have never been to one, it would be great to stay in a Japanese inn (ryokan) for at least a night. There are some in Tokyo that are not pricey at all. You might look at
http://www2.dango.ne.jp/kimi/ryokan.html
http://www.libertyhouse.gr.jp
http://www.tamaryokan.com
http://www.tokyoryokan.com
http://www.toukaisou.com

When I really needed a cheap place to stay in Tokyo, I stayed in a 4 people dorm at Sakura Hostel Asakusa. Cheapest I've ever had in Tokyo. Clean - 2940 yen, English speaking staff and nice mood in the public area.

http://www.sakura-hotel.co.jp/asakusa

i cosign sakura.