Hi,
To address your projection issue I can not give you a straight answer as I know nothing about picking a projection for big areas of the amazon, but this is essentially your problem. Your data is in a Geographic Coordinate System this system essentially describes the location of a place on a sphere in degrees (latitude longitude) and it just does not make sense to do any analysis on this as the degrees are not a uniform measurement (1 deg at the equator covers more distance then one deg at the north pole).
That is where projections come in they are a mathematical way to transform the GCS onto a flat surface. But just like peeling an orange you cannot do this without distorting measurements, including distance, shape, area and angles. That is why there are so many different projections, they are useful for different things. I usually work in a single UTM zone, but you are working on the whole amazon which spans many UTM zones ao that is not the answer. I think in the end you will just need to do some research and find a projection that distorts the variable of concern (distance) the least for your study area, but whatever the solution is I doubt it will be perfect.
You can check out this book, some parts are pretty technical but other parts are not, I think it is good, Datums and map projections for remote sensing, GIS, and surveying By Jonathan Iliffe
For as to why your data does not change projections when you try, you might want to read up on on the fly projecting in arcgis. What I usually do is go; view data frame properties and set the projection I want. Then export a copy of my files in this projection, open a new map (clears the projection) then add my projected data. There are a lot of ways to achieve this though ex project tool.
As for the second part of your question. There is also no definite answer and it depends on what you want to know. If all of your features have a neighbour within 20km except one that is 500km away then you could miss some important trends. What I would do (if using arcGIS 10) the ISA outputs messages to the geoprocessing results thing, in there it reports the number of features that did not have a neighbour. Using this you can come up with a logical choice that is defendible.
David