Create a Cube in Blender from Python
You have to create the object with an empty mesh first, as you cannot assign a mesh to an empty later.

Further: primitive_cube_add(...) is supposed to create an object, since it is the same operator called by Add->Mesh->Cube from the menu.

So you can use BMesh to create your cube later and assign it to the empty mesh:

import bpy
import bmesh

bpyscene = bpy.context.scene

# Create an empty mesh and the object.
mesh = bpy.data.meshes.new('Basic_Cube')
basic_cube = bpy.data.objects.new("Basic_Cube", mesh)

# Add the object into the scene.
bpyscene.objects.link(basic_cube)
bpyscene.objects.active = basic_cube
basic_cube.select = True

# Construct the bmesh cube and assign it to the blender mesh.
bm = bmesh.new()
bmesh.ops.create_cube(bm, size=1.0)
bm.to_mesh(mesh)
bm.free()