This issue was fixed by compiling with cmake.

cmake_minimum_required(VERSION 2.6)

find_library(LIB_STAGE stage PATHS /usr/local/lib)
include_directories(/usr/local/include/Stage-4.1/)
add_executable(stage_test stage_test.cpp)
target_link_libraries(stage_test ${LIB_STAGE})