No idea why you have that issue, or what the issue exactly is because "people cannot subscribe" is not really a helpful description of symptoms; what I can tell you is that I know with 100% certainty that e.g. Subscribe2 (to subscribe to new entries/posts) and Subscribe to Comments (does what the name suggests) both work fine on BlueHost.
One thing you have to keep in mind though: BlueHost is very finicky about mass email, so if you have (say) more than 100 subscribers, you'd do well to contact BH tech support (see your cPanel for various contact methods) to relax the restriction on the number of allowed recipients. Also, if you have a large number of subscribers (say, over 1,000) you will have to stagger the mailing. E.g. in Subscribe2 and several other well-written "update notifier" plugins you can throttle emails by sending them in hourly batches. If your subscriptions are through the roof, may want to consider a different solution, via an external provider, e.g. Constant Contact (although that is for email newsletters, and not for update notifications).
