Yeah not all IOS image feature sets support the 6in4 tunneling needed to use a HE.net tunnel. This is probably my biggest annoyance with Cisco routers. There are so may little "gotchas" when it comes to certain images only supporting certain things.
I know that the enterprise feature set images have 6in4 since that's what I use. Of course they tend to include everything, even the kitchen sink, so the enterprise images can be a bit pricey if you license them from Cisco like you are supposed to. Other than that I would assume that the ip plus and advanced ip services feature sets probably have them too. The IOS feature navigator is probably your best resource here. You can also check out
this post.
If you would rather just buy another router then a 2621xm from ebay would probably be one of the cheapest options. With enough installed memory it can run 12.4 enterprise which works perfectly with HE.net. It only pushes about 22-24 mbps though. If you need something with more throughput you could look at a 3725 or 3745. Any of the three will do a 6in4 tunnel, assuming you are able to get the appropriate IOS images for them anyway.
Newer models such as the 1800 and 2800 lines will also do 6in4 of course (with the proper IOS image) but they are a good bit more expensive.
