Okay, let's see if we can break this down.
First off, we need to define "Religion" here. And, probably predictibly, most are defining it according to the culture that they were raised in, rather than a larger look at the concept. So let's broaden things a bit, shall we?
Religion, in it's essence, is a source of governing values and morals providing a way of approaching, or living, your life. You may note that I'm not mentioning any form of Deity here. The reason for that is that although there is typically a central figure, or a group of central figures, they are materialistically only a way of expressing the teachings and lessons of the particular religion itself. So religion is really just a way to learn to live.
The methods that are used include stories, rituals, symbolic actions, specific attributes or tools and other items, and so on. These things, these lessons on life, give rise to a religion. After all, religion is our natural responce to "Who are we? Why are we here?" and other big, important questions.
Without getting into the concepts of the existance of God, Gods, or any other such, I would simply say that God is the answer to many of these questions in a religious sense. This of course gets into the concepts of faith versus proof, experience as individual proof, and so on, but that is not the discussion here. To head that potential tangent off, whatever an individuals personal relationship with God, Gods, or some other is, that is true and valid for them, and as such cannot be disproven. Nor should it be. But really, that's kinda beside the point of what a religion is.
So what is it? Well, a religion is a formalised system of lessons expressed through a belief system, and is not necessarily supernatural in form. These lessons are designed to teach the values of the religion, not the faith many associate with one. This is why someone may say "That's not very Christian of you...", which means it doesn't follow the lessons and values, not "that's not very supportive of the belief that Jesus was the Messiah, He died for your sins, that you may know the paradise that the Heavenly Father has prepared for you and all saved souls..."
Now, there are differences between various religions, obviously. The forms and rituals followed vary, as do obviously the beliefs it expresses itself through and by. But there are also differences between Eastern and Western religions (being very general here!). For example, Western religions are based on an external focal point (God, Jesus, Moses, Mohammed), using those as centralising concepts that the values and lessons are expressed through. Culturally, these religions tend to be exclusive (you can't follow more than one), mainly as each is purporting to have the answer... and if one has the answer, the other answers can't, by definition, be the right ones. The focus is on the individual, and their relationship with their expression of God (personal, as discussed earlier). Western cultures also tend to be focused on "guilt" as a controlling mechanism.
Eastern religions are more focused on the concepts of the world around them, with religions such as Shinto being a form of reverence to the natural world around you, and lessons taken from there, as well as reverence towards your ancestors (we'll come back to that...), Confucianism and Taoism being ways of approaching life with an ideal "perfect" behaviour (which is an expression of the underlying values and beliefs), Buddhism, which focuses on becoming almost as non-invasive into the world as possible. These concepts can be applied by one person easily (paying reverance to your ancestors while approaching life with an ideal behaviour, and so on) with no conflict. Whereas the Western approach focuses on the individual and a personal relationship with the Divine, an Eastern approach is more focused on placement within a group, and the controlling mechanism is "shame".
Now, when we are discussing the concept of the Bujinkan (or Ninjutsu, or any Japanese martial art) having religious aspects, overtones, influences, or anything else, these distinctions should be kept in mind. And, for the record DuskB4Dawn, religious aspects would be considered more likely than not in any old system, Katori Shinto and Shinto Muso Ryu both contain the religious concept of Shinto in their very names (with Katori being one of the two most famous Shinto Shrines in Japan, and Shinto Muso Ryu being founded by a member of the Katori Ryu), along with Kashima Shinryu (Kashima being the other major Shinto Shrine, and the founder being again a member of the Katori Ryu) are highly influenced by Shinto, others are very influenced by Buddhism, such as Hyoho Niten Ichi Ryu, and so on. There have been various religious aspects associated with different Ninjutsu traditions as well. Even the opening phrase of most Ninjutsu schools "Shikin Haramitsu Daikomyo" is described as a prayer from Kumogakure Ryu.
As a result, the Bujinkan looking to be a religious organisation doesn't actually impeach on Christian doctrine (Thou shalt have no Gods before me, and other doctrine) as the concept of "religion" is rather different to the Western variant. The other important thing to realise is the exact wording here... the Bujinkan is not looking to become a religion, per se, but a religious organisation. There's a subtle difference there, really. If you are Christian (or any other Western, exclusive doctrine religion), you are not then following another religion, you have simply become part of a separate organisation, not another religion. It's a small difference, but it's there.
